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$
6
  • $\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, 2017 at 10:04
  • 1
    $\begingroup$ Programming questions are off-topic here. $\endgroup$ Jan 15, 2017 at 11:08
  • 2
    $\begingroup$ Heads up: There can be an exponential number of shortest paths between two vertices. $\endgroup$
    – orezvani
    Jan 15, 2017 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, 2017 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, 2017 at 12:00

0

Browse other questions tagged or ask your own question.