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 pathforeach(array_keys($_distArr) as $val) $Q[$val] = 99999;$Q[$a] = 0;//start calculatingwhile(!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 resultecho <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);
Dijkstra's algorithm in PHP
php;algorithm;graph
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!