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);

migrated from stackoverflow.com Jan 4 '15 at 17:00

This question came from our site for professional and enthusiast programmers.

  • 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
up vote 4 down vote accepted

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!

  • 1
    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.

protected by Jamal May 3 at 2:23

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.