PHP Classes

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    
Ratings Unique User Downloads Download Rankings
Not enough user ratingsTotal: 274 All time: 7,660 This week: 136Up
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.

Picture of Lionel F. Lebeau
  Performance   Level  
Name: Lionel F. Lebeau <contact>
Classes: 4 packages by
Country: France France
Age: 63
All time rank: 245268 in France France
Week rank: 312 Up15 in France France Up
Innovation award
Innovation award
Nominee: 2x

Example

<?php
setlocale
(LC_ALL, 'en_GB.UTF8');
$time_start = microtime(true);
set_time_limit(0);
require_once
__DIR__.'/constantes.php';
require_once
__DIR__.'/class.dictionnaires.php';
$dictionnaire = new dictionnaire('en_GB.UTF-8');
$dictionnaire->get_fichiers(array(__DIR__.'/langages/en_GB.UTF-8/en_GB.UTF-8.xml'));
require_once
__DIR__.'/class.graph.php';
?>
<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8"/>
        <title><?php print i18N_T("Graph");?></title>
        <link rel="stylesheet" href="/graph/css/commun.css" media="screen"/>
        <script async="async" src="/graph/js/commun.js"></script>
    </head>
    <body>
        <h1><?php print i18N_T("Chemin le plus court");?></h1>
        <p><?php print i18N_T("Calcul du chemin le plus court (en distance ou temps) entre deux villes");?><br />
        <details>
            <summary><?php print i18N_T("Les codes utilisés sont ceux de villes d'Australie");?></summary>
            <ul>
                <li>ADL : Adelaide</li>
                <li>ASP : Alice Springs</li>
                <li>BNE : Brisbane</li>
                <li>CBR : Canberra</li>
                <li>CNS : Cairns</li>
                <li>DRW : Darwin</li>
                <li>MEL : Melbourne</li>
                <li>PER : Perth</li>
                <li>SYD : Sydney</li>
            </ul>
        </details></p>
<?php
//$graph = new graph('ADL', 'PER', DIST);
//$graph = new graph('ADL', 'PER', TEMPS);
$graph = new graph('SYD', 'PER', DIST);
//$graph = new graph('SYD', 'PER', TEMPS);
//$graph = new graph('MEL', 'CNS', DIST);
//$graph = new graph('MEL', 'CNS', TEMPS);
//$graph = new graph('SYD', 'DRW', DIST);
//$graph = new graph('SYD', 'DRW', TEMPS);
//$graph = new graph('MEL', 'DRW', DIST);
//$graph = new graph('MEL', 'DRW', TEMPS);
//$graph = new graph('PER', 'BNE', DIST);
//$graph = new graph('PER', 'BNE', TEMPS);
if(count($graph->collectionOK)>0){
    foreach(
$graph->collectionOK as $cle => $branche){
        if(
$graph->type==DIST){
           
printf(i18N_T("La distance entre %s et %s est de %.2f km"),$graph->vd,$graph->va,$branche->get_distTot());
            print
'<br />'.i18N_T("Le circuit le plus court est :").'<br />';
            foreach(
$branche->liste as $key => $chemin){
               
printf("%s -> %s [%.2f km]",$chemin->ville1,$chemin->ville2,$chemin->dist);
                print
'<br />';
            }
        }elseif(
$graph->type==TEMPS){
           
$heures = floor($branche->get_tempsTot()/60);
           
$minutes = $branche->get_tempsTot() % 60;
           
$duree = ($minutes > 0)?$heures.' heures '.$minutes.' minutes':$heures.' heures';
           
printf(i18N_T("La distance entre %s et %s est de %s"),$graph->vd,$graph->va,$duree);
            print
'<br />'.i18N_T("Le circuit le plus rapide est :").'<br />';
            foreach(
$branche->liste as $key => $chemin){
               
printf("%s -> %s [%s]",$chemin->ville1,$chemin->ville2,str_replace('.',' h ',$chemin->temps));
                print
'<br />';
            }
        }
    }
}else{
    if(
$graph->get_Graph()){
        if(!
DEBUG){
            unset(
$graph->collection,$graph->omits);
        }
        if(
DEBUG){
           
$graph->affiche_Graph();
        }
       
$graph->count = count($graph->collectionOK);
        if(
$graph->count > 0){
            foreach(
$graph->collectionOK as $cle => $branche){
                if(
$graph->type==DIST){
                   
printf(i18N_T("La distance entre %s et %s est de %.2f km"),$graph->vd,$graph->va,$branche->get_distTot());
                    print
'<br />'.i18N_T("Le circuit le plus court est :").'<br />';
                    foreach(
$branche->liste as $key => $chemin){
                       
printf("%s -> %s [%.2f km]",$chemin->ville1,$chemin->ville2,$chemin->dist);
                        print
'<br />';
                    }
                }elseif(
$graph->type==TEMPS){
                   
$heures = floor($branche->get_tempsTot()/60);
                   
$minutes = $branche->get_tempsTot() % 60;
                   
$duree = ($minutes > 0)?$heures.' heures '.$minutes.' minutes':$heures.' heures';
                   
printf(i18N_T("La distance entre %s et %s est de %s"),$graph->vd,$graph->va,$duree);
                    print
'<br />'.i18N_T("Le circuit le plus rapide est :").'<br />';
                    foreach(
$branche->liste as $key => $chemin){
                       
printf("%s -> %s [%s]",$chemin->ville1,$chemin->ville2,str_replace('.',' h ',$chemin->temps));
                        print
'<br />';
                    }
                }
               
$sql= "INSERT INTO chemins
                    (ville1,ville2,dist,temps,etapes,comp)
                    VALUES(\""
.$graph->vd."\",\"".$graph->va."\",\"".number_format($branche->get_distTot(),1,'.','')."\",\"".$branche->get_tempsTot()."\",'".json_encode($branche->liste,JSON_HEX_APOS|JSON_HEX_QUOT|JSON_PRESERVE_ZERO_FRACTION)."',".$graph->type.")";
               
$graph->enregChemin($sql);
            }
        }else{
            print
$graph->message.'<br />';
        }
    }else{
        print
$graph->message.'<br />';
    }
}
$time_end = microtime(true);
$time = $time_end - $time_start;
print
"<br />Durée : ".$time." secondes<br />";
?>
</body>
</html>


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:274
This week:0
All time:7,660
This week:136Up
User Comments (1)
nice
7 years ago (muabshir)
80%StarStarStarStarStar