PHP Classes
elePHPant
Icontem

PHP Shortest Path Algorithm: Compute the shortest route between two points

Recommend this page to a friend!
  Info   View files Example   View files View files (8)   DownloadInstall with Composer Download .zip   Reputation   Support forum (1)   Blog    
Last Updated Ratings Unique User Downloads Download Rankings
2016-10-03 (3 years ago) RSS 2.0 feedNot enough user ratingsTotal: 228 All time: 7,961 This week: 338Up
Version License PHP version Categories
graphsolver 1.0.0GNU General Publi...5Algorithms, PHP 5, Geography
Description Author

This class can compute the shortest route between to points.

It can take the names of start and end location and finds the shortest path using an algorithm loosely based on Dijkstra’s algorithm.

The paths between locations and them distance and time it takes to go from one to the other are retrieved from a MySQL database.

Instead of trying to resolve each branch of the tree, it computes the nearest nodes.

If a result is found, it is memorized. Then other solutions are searched.
If a shorter one is found, it replaces the longer one and eliminates the corresponding branch. If a longer one is found, the branch is eliminated.
If an equal one through a different route is found, it is added.

The package includes a class for localizing some text messages.

  Performance   Level  
Name: Lionel F. Lebeau <contact>
Classes: 4 packages by
Country: France France
Age: 58
All time rank: 252569 in France France
Week rank: 664 Up24 in France France Up
Innovation award
Innovation award
Nominee: 2x

 

Details
If you don't want to use the i18N_T package, you'll have to replace all the calls to i18N_T() by gettext(), intl fonctions, or by sentences in your own language.

This class is reasonably fast as once it has found solutions, they are recorded in the "chemins" table.
You can, of course, rename the database, the tables and the fields to fit your habits.
Once you are decided, you'll have to change the default values in constantes.php

This class takes three parameters as input :
the  start point
the end point
the way the calculation is effectued (distance or time).
It returns a graph object containing the collection of results (in collectionOK).

Temporary branches are kept in list objets with the "liste" class (class.liste.php).

This class tries to get rid of bad branches very quick to make the search faster.

One important point : when adding records in th "vvd" table, always add the two directions (eg : A -> B and B-> A).
The class knows which one it must use in a branche so that it doesn't loop.

The "graph" class (class.graph.php) could be adapted for many other uses.
  Files folder image Files  
File Role Description
Files folder imagelangages (2 directories)
Plain text file class.graph.php Class Main class
Plain text file class.liste.php Class Sub class for the lists
Accessible without login Plain text file constantes.php Conf. Defines constantes
Accessible without login Plain text file graph.php Example A basic example
Accessible without login Plain text file graph.sql Data Database source
Accessible without login Plain text file readme Doc. readme

  Files folder image Files  /  langages  
File Role Description
Files folder imageen_GB.UTF-8 (1 file)
Files folder imagefr_FR.UTF-8 (1 file)

  Files folder image Files  /  langages  /  en_GB.UTF-8  
File Role Description
  Accessible without login Plain text file en_GB.UTF-8.xml Data Auxiliary data

  Files folder image Files  /  langages  /  fr_FR.UTF-8  
File Role Description
  Accessible without login Plain text file fr_FR.UTF-8.xml Data Auxiliary data

Downloadgraphsolver-2016-10-03.zip 8KB
Downloadgraphsolver-2016-10-03.tar.gz 6KB
Install with ComposerInstall with Composer
Needed packages  
Class DownloadWhy it is needed Dependency
PHP i18N Library Download .zip .tar.gz For using translation Optional
 Version Control Unique User Downloads Download Rankings  
 25%
Total:228
This week:0
All time:7,961
This week:338Up
User Comments (1)
nice
3 years ago (muabshir)
80%StarStarStarStarStar