0
$\begingroup$

I found a code in the internet for Dijkstra's shortest path algorithm in PHP. The problem is it only shows one possible path. If there are several paths having the same distance, it only outputs one of them.

How can I modify this algorithm to produce all shortest paths?

//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 = 6;

//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 "
From $a to $b"; echo "
The length is ".$S[$b][1]; echo "
Path is ".implode('->', $path);

?>

$\endgroup$
  • $\begingroup$ There's no search algorithm in the code you showed, only what seems to be the steps to print the path once it's been calculated. $\endgroup$ – giusti Jan 15 '17 at 10:04
  • 1
    $\begingroup$ Programming questions are off-topic here. $\endgroup$ – Yuval Filmus Jan 15 '17 at 11:08
  • 2
    $\begingroup$ Heads up: There can be an exponential number of shortest paths between two vertices. $\endgroup$ – orezvani Jan 15 '17 at 11:11
  • $\begingroup$ For example, if all the distances are zero, so each path is a shortest path. That even gives you an infinite number of shortest paths. $\endgroup$ – gnasher729 Jan 15 '17 at 11:47
  • 1
    $\begingroup$ Welcome to Computer Science! Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Jan 15 '17 at 12:00