PHP Classes

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

Recommend this page to a friend!
     
  Info   Example   View files Files   Install with Composer Install with Composer   Download Download   Reputation   Support forum   Blog    
Ratings Unique User Downloads Download Rankings
Not enough user ratingsTotal: 275 All time: 7,664 This week: 560Up
Version License PHP version Categories
graphsolver 1.0.0GNU General Publi...5Algorithms, PHP 5, Geography
Description 

Author

Lionel F. Lebeau

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

Level 3 StarStarStar

 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 (8)  
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 (8)  /  langages  
File Role Description
Files folder imageen_GB.UTF-8 (1 file)
Files folder imagefr_FR.UTF-8 (1 file)

  Files folder image Files (8)  /  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 (8)  /  langages  /  fr_FR.UTF-8  
File Role Description
  Accessible without login Plain text file fr_FR.UTF-8.xml Data Auxiliary data

The PHP Classes site has supported package installation using the Composer tool since 2013, as you may verify by reading this instructions page.
Install with Composer Install with Composer
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:275
This week:0
All time:7,664
This week:560Up
User Comments (1)
nice
8 years ago (muabshir)		80%StarStarStarStarStar
 

  Applications that use this package  
No pages of applications that use this class were specified.

Add link image If you know an application of this package, send a message to the author to add a link here.