# 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.. – Potherca Jul 15 '15 at 19:47
• Looks really pretty. – coderodde Jul 29 '15 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"). – SirPython Jul 22 '15 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.