Dijkstra.php

<?php
class BS_Dijkstra
{
	private $_mapGraph;
	private $_startId;
	private $_mapDistance = array();
	private $_mapPrevious = array();
	
	public function __construct($mapGraph, $startId)
	{
		$this->_mapGraph = $mapGraph;
		$this->setStart($startId);
	}
	
	public function setStart($startId)
	{
		$this->_startId = $startId;
		$visited = array();
		
		$this->_mapDistance = array();
		$this->_mapPrevious = array();
		
		foreach($this->_mapGraph AS $key => $location) {
			$this->_mapDistance[$key] = INF;
			$visited[$key] = false;
			$this->_mapPrevious[$key] = null;
		}
		
		$Q = array();
		
		if(!isset($this->_mapGraph[$startId])) {
			return;
		} else {
			$Q[$startId] = $this->_mapGraph[$startId];
			$this->_mapDistance[$startId] = 0;
		}
		
		while(count($Q) > 0) {
			$u = null;
			foreach($Q as $key => $unvisited) {
				if($u === null || $this->_mapDistance[$key] < $this->_mapDistance[$u]) {
					$u = $key;
				}
			}
			
			unset($Q[$u]);
			$visited[$u] = true;
			
			foreach($this->_mapGraph[$u] as $gateway) {
				list($target, $distance) = $gateway;
				$alt = $this->_mapDistance[$u] + $distance;
				
				if(!isset($this->_mapDistance[$target]) || $alt < $this->_mapDistance[$target]) {
					$this->_mapDistance[$target] = $alt;
					$this->_mapPrevious[$target] = $u;
					if(!$visited[$target]) {
						$Q[$target] = $this->_mapGraph[$target];
					}
				}
			}
		}
	}
	
	public function getDistance($nodeId)
	{
		return isset($this->_mapDistance[$nodeId]) ? $this->_mapDistance[$nodeId] : 99999;
	}
	
	public function getDistanceMap()
	{
		return $this->_mapDistance;
	}
	
	public function getDistanceMapWithin($max) 
	{
		return $this->getDistanceMapBetween(0,$max);
	}
	
	public function getDistanceMapBetween($min, $max) 
	{
		$map = array();
		foreach($this->_mapDistance as $key => $distance) {
			if($distance <= $max && $distance >= $min) {
				$map[$key] = $distance;
			}
		}
		return $map;
	}
	
	public function getRoute($endId)
	{
		$path = array();
		$u = $endId;
		
		while(isset($this->_mapPrevious[$u])) {
			array_unshift($path, $u);
			$u = $this->_mapPrevious[$u];
		}
		array_unshift($path, $u);
		
		return $path;
	}
}

DijkstraDemoGraph.php

<?php

$graph = json_decode('{"1":[[35,1]],"2":[[10,12]],"3":[[10,12],[4,1],[9,1]],"4":[[3,1]],"5":[[10,12],[9,1]],"6":[[9,1],[10,12]],"7":[[10,12],[94,1]],"8":[[9,1]],"9":[[12,1],[8,1],[6,1],[5,1],[3,1]],"10":[[13,1],[107,12],[2,12],[5,12],[3,12],[14,1],[11,1],[7,12],[39,12],[6,12],[118,12]],"11":[[10,1]],"12":[[9,1]],"13":[[10,1]],"14":[[42,1],[10,1]],"15":[[19,12],[17,12]],"16":[[19,1]],"17":[[21,12],[15,12]],"18":[[20,1],[19,12]],"19":[[15,12],[16,1],[18,12],[111,12]],"20":[[62,1],[21,1],[18,1]],"21":[[20,1],[17,12]],"22":[[32,1],[36,1]],"23":[[25,1],[83,1]],"24":[[34,1],[35,1]],"25":[[108,12],[23,1],[31,1],[36,12],[33,1],[27,1]],"26":[[35,1],[147,1]],"27":[[25,1]],"28":[[31,1]],"29":[[32,1],[35,1]],"30":[[36,1]],"31":[[28,1],[25,1]],"32":[[29,1],[33,1],[22,1]],"33":[[32,1],[25,1]],"34":[[164,1],[24,1]],"35":[[24,1],[36,12],[26,1],[140,12],[29,1],[1,1]],"36":[[65,12],[35,12],[30,1],[22,1],[25,12]],"37":[[45,12],[44,1],[39,12],[48,12],[50,1],[110,12]],"38":[[48,1]],"39":[[37,12],[47,12],[42,1],[10,12]],"40":[[42,1]],"41":[[48,1]],"42":[[40,1],[39,1],[14,1]],"43":[[47,1]],"44":[[37,1]],"45":[[37,12],[54,12],[49,12]],"46":[[55,1]],"47":[[43,1],[39,12],[53,1],[56,12],[48,12]],"48":[[55,12],[37,12],[47,12],[41,1],[38,1]],"49":[[45,12],[78,1],[54,12]],"50":[[37,1]],"51":[[55,1]],"52":[[56,12],[55,12],[54,12],[127,12]],"53":[[47,1]],"54":[[45,12],[55,12],[81,12],[52,12],[49,12]],"55":[[51,1],[52,12],[46,1],[54,12],[48,12],[58,1],[57,1],[56,12]],"56":[[52,12],[47,12],[59,1],[55,12]],"57":[[55,1]],"58":[[55,1]],"59":[[56,1],[128,1]],"60":[[79,1],[67,12],[74,12],[65,12]],"61":[[63,1],[69,1],[162,1]],"62":[[66,1],[71,1],[76,1],[20,1]],"63":[[67,1],[61,1]],"64":[[77,1],[79,1],[80,1]],"65":[[60,12],[77,12],[36,12]],"66":[[62,1],[77,1]],"67":[[80,1],[60,12],[69,12],[75,1],[63,1],[68,1],[80,1],[80,1]],"68":[[67,1]],"69":[[67,12],[70,12],[72,1],[61,1]],"70":[[81,12],[69,12],[132,12]],"71":[[62,1],[80,1],[78,1]],"72":[[73,1],[69,1]],"73":[[81,1],[72,1],[80,1]],"74":[[60,12],[75,1],[147,1]],"75":[[67,1],[74,1],[159,1]],"76":[[62,1],[88,1]],"77":[[64,1],[65,12],[66,1],[105,12]],"78":[[81,1],[71,1],[49,1]],"79":[[60,1],[64,1]],"80":[[67,1],[71,1],[73,1],[67,1],[67,1],[64,1]],"81":[[70,12],[73,1],[78,1],[54,12]],"82":[[93,1],[92,1]],"83":[[93,1],[23,1]],"84":[[109,1],[96,1]],"85":[[100,1],[93,1]],"86":[[104,1],[99,1],[93,12],[102,1],[97,1],[107,12]],"87":[[100,1],[105,1]],"88":[[95,12],[76,1],[105,12]],"89":[[95,1],[100,1]],"90":[[95,1],[100,1]],"91":[[109,1],[96,1]],"92":[[96,1],[98,1],[100,1],[82,1]],"93":[[86,12],[85,1],[83,1],[108,12],[82,1]],"94":[[107,1],[107,1],[7,1]],"95":[[90,1],[105,12],[89,1],[109,12],[88,12],[98,1]],"96":[[102,1],[99,1],[92,1],[103,1],[97,1],[84,1],[104,1],[106,1],[91,1]],"97":[[96,1],[86,1]],"98":[[95,1],[92,1]],"99":[[86,1],[96,1]],"100":[[90,1],[85,1],[87,1],[89,1],[92,1]],"101":[[108,1]],"102":[[96,1],[86,1]],"103":[[96,1],[109,1]],"104":[[86,1],[96,1]],"105":[[95,12],[77,12],[108,12],[88,12],[87,1]],"106":[[109,1],[96,1]],"107":[[109,12],[94,1],[94,1],[86,12],[10,12]],"108":[[101,1],[93,12],[105,12],[25,12]],"109":[[84,1],[107,12],[95,12],[106,1],[91,1],[103,1],[117,12]],"110":[[37,12],[118,1]],"111":[[115,1],[118,1],[114,1],[19,12],[112,1],[113,1]],"112":[[116,1],[111,1]],"113":[[111,1]],"114":[[111,1]],"115":[[111,1],[116,1]],"116":[[112,1],[115,1]],"117":[[109,12],[118,1]],"118":[[111,1],[117,1],[110,1],[10,12]],"119":[[127,1]],"120":[[132,12],[124,1],[121,1],[125,1],[130,1],[157,12]],"121":[[120,1],[162,1]],"122":[[133,1],[129,1]],"123":[[125,1],[145,1]],"124":[[120,1]],"125":[[120,1],[123,1]],"126":[[134,1]],"127":[[134,1],[132,12],[128,1],[52,12],[131,1],[119,1]],"128":[[59,1],[127,1]],"129":[[130,1],[122,1],[131,1]],"130":[[129,1],[120,1]],"131":[[129,1],[127,1]],"132":[[120,12],[127,12],[133,1],[70,12]],"133":[[122,1],[132,1]],"134":[[127,1],[126,1]],"135":[[137,1],[138,1]],"136":[[143,1],[152,12],[138,1]],"137":[[135,1],[154,1]],"138":[[154,1],[136,1],[142,1],[148,1],[150,1],[135,1],[151,1]],"139":[[162,1],[152,12]],"140":[[144,12],[35,12]],"141":[[148,1]],"142":[[145,1],[138,1]],"143":[[136,1]],"144":[[140,12],[156,12],[148,12],[149,1],[158,12]],"145":[[142,1],[123,1]],"146":[[161,1],[152,12]],"147":[[158,1],[156,1],[74,1],[26,1]],"148":[[138,1],[144,12],[141,1]],"149":[[144,1]],"150":[[153,1],[138,1]],"151":[[164,1],[138,1]],"152":[[157,12],[160,1],[136,12],[163,1],[146,12],[139,12]],"153":[[150,1]],"154":[[138,1],[137,1]],"155":[[156,1]],"156":[[144,12],[147,1],[155,1]],"157":[[152,12],[120,12]],"158":[[159,1],[147,1],[144,12]],"159":[[158,1],[161,1],[75,1]],"160":[[152,1]],"161":[[146,1],[159,1]],"162":[[139,1],[61,1],[121,1]],"163":[[152,1]],"164":[[151,1],[34,1]]}',true);