Dijkstra's algorithm in PHP

This is Dijkstra's algorithm in PHP. Regarding the data structure, I use a 2-dimensional array $_distArr[m][n]=length to store it. Are there any improvements for this? $a and $b are the start and the end node, respectively. <?php /** * Dijkstra's algorithm in PHP by zairwolf * * Demo: http://www.you4be.com/dijkstra_algorithm.php * * Source: https://github.com/zairwolf/Algorithms/blob/master/dijkstra_algorithm.php * * Author: Hai Zheng @ https://www.linkedin.com/in/zairwolf/ * */ //set the distance array$_distArr = array();
$_distArr[1][2] = 7;$_distArr[1][3] = 9;
$_distArr[1][6] = 14;$_distArr[2][1] = 7;
$_distArr[2][3] = 10;$_distArr[2][4] = 15;
$_distArr[3][1] = 9;$_distArr[3][2] = 10;
$_distArr[3][4] = 11;$_distArr[3][6] = 2;
$_distArr[4][2] = 15;$_distArr[4][3] = 11;
$_distArr[4][5] = 6;$_distArr[5][4] = 6;
$_distArr[5][6] = 9;$_distArr[6][1] = 14;
$_distArr[6][3] = 2;$_distArr[6][5] = 9;

//the start and the end
$a = 1;$b = 5;

//initialize the array for storing
$S = array();//the nearest path with its parent and weight$Q = array();//the left nodes without the nearest path
foreach(array_keys($_distArr) as$val) $Q[$val] = 99999;
$Q[$a] = 0;

//start calculating
while(!empty($Q)){$min = array_search(min($Q),$Q);//the most min weight
if($min ==$b) break;
foreach($_distArr[$min] as $key=>$val) if(!empty($Q[$key]) && $Q[$min] + $val <$Q[$key]) {$Q[$key] =$Q[$min] +$val;
$S[$key] = array($min,$Q[$key]); } unset($Q[$min]); } //list the path$path = array();
$pos =$b;
while($pos !=$a){
$path[] =$pos;
$pos =$S[$pos][0]; }$path[] = $a;$path = array_reverse($path); //print result echo "<img src='http://www.you4be.com/dijkstra_algorithm.png'>"; echo "<br />From$a to $b"; echo "<br />The length is ".$S[$b][1]; echo "<br />Path is ".implode('->',$path);

• Could you define what kind of "improvement" you are hoping to find? At first glance there are quality, readability and speed improvements possible for this piece of code.. Jul 15, 2015 at 19:47
• Looks really pretty. Jul 29, 2015 at 6:19

This implementation is great and works well, but you should add an "escape door" when no path is found.

For instance, remove these two lines:

$_distArr[4][5] = 6; ...$_distArr[6][5] = 9;


If you comment both lines, you enter an infinite loop.

To avoid this problem, I think you can add these lines right before the "calculating while" loop:

if (!array_key_exists($b,$S)) {
echo "Found no way.";
return;
}


Then you're set; no infinite loop!

• Nice review! Just for the future, answers should not be left in comments; answers are meant for answers. (I am mentioning this because you wrote "I cannot comment so I'm answering"). Jul 22, 2015 at 12:51

Implementation works well. Please note, your code assumes all edges are bi-directional with the statement below:

foreach(array_keys($_distArr) as$val) $Q[$val] = 99999;


If you add $_distArr[6][7] = 1; and change $b = 5; to $b = 7, then you will get an error because 7 is not inserted in $Q.