Dijkstra algorithm problem

[engahmed]

Hello

 

I'm using Dijkstra algorithm in my graduation project to find the shortest route between two points and then display it on google maps

 

I found that code but i can't modify it with my needs

 

Here is the original code

<?php

/**
* Dijkstra algorithm node class
*
* @author Mallory Dessaintes - [email protected]
*/

class DijkstraNode {
	const IMPOSSIBLE_DIST = -1;

	protected $_id;
	protected $_neighbours = array();
	protected $_distToSource = self::IMPOSSIBLE_DIST;

	protected static $_nodes = array();

	public function __construct($id,$links = array()) {
		$this->_id = $id;
		$this->_neighbours = $links;

		static::$_nodes[] = $this;
	}

	/**
	* Return all the nodes created
	*/
	public static function getNodes() {
		return static::$_nodes;
	}

	/**
	* Add a neighbour to the node, specifying the distance between it and the current node
	*
	* @param bool $reciprocally Current node is also add as a neighbour of the given node
	*/
	public function addNeighbour(DijkstraNode $node,$dist = 1,$reciprocally = true) {
		if(!isset($this->_neighbours[$node->_id])) {
			$this->_neighbours[$node->_id] = array('node' => $node, 'dist' => $dist);

			if($reciprocally) {
				$node->_neighbours[$this->_id] = array('node' => $this, 'dist' => $dist);
			}
		}
		else {
			trigger_error('Neighbour already exists');
		}
	}

	/**
	* Return the neighbours of the node
	*/
	public function getNeighbours() {
		return array_values($this->_neighbours);
	}

	/**
	* Return the distance between the current node and another node (normally a neighbour node)
	*/
	public function getNeighbourDist(DijkstraNode $node) {
		if($node == $this) {
			return 0;
		}
		else {
			if(isset($this->_neighbours[$node->_id])) {
				return $this->_neighbours[$node->_id]['dist'];
			}
			else {
				// Node is not a neighbour
				return self::IMPOSSIBLE_DIST;
			}
		}
	}

	public function getId() {
		return $this->_id;
	}

	public function getDistToSource() {
		return $this->_distToSource;
	}

	public function setDistToSource($val) {
		$this->_distToSource = $val;
	}
}

/**
* Main Dijkstra algorithm class
*
* @author Mallory Dessaintes - [email protected]
*/
class Dijkstra {
	protected static $_preds; // predecessors of the nodes
	protected static $_toVisit; // nodes to visit
	protected static $_visited; // nodes already visited
	protected static $_source; // Source node

	/**
	* Use Dijkstra algorithm to find the best route between source and all the nodes
	*
	* @param array $nodes All the nodes, including the source
	* @param DijkstraNode $source The source node
	* (we just use it to set the distance between it and "source" to 0, of course) and get a starting point
	*
	* @return
	*/
	public static function findRoute($nodes,DijkstraNode $source) {
		static::$_toVisit = $nodes;
		static::$_source = $source;

		static::_init();

		while(count(static::$_toVisit)) {
			static::_sortNodes();
			$node = static::$_toVisit[0];

			// Remove the current node from nodes to visit
			unset(static::$_toVisit[array_search($node,static::$_toVisit)]);

			// Test if have already found a path to this this which must be done ewcept if there iq no path
			if($node->getDistToSource() != DijkstraNode::IMPOSSIBLE_DIST) {

				// Foreach neighbours of the current node
				foreach($node->getNeighbours() as $neighbourData) {
					$neighbour = $neighbourData['node']; // $neighbourData['dist'] = the distance between the node and this neighbour

					// Only if we doesn't already visited it (because if we had, the last past was necessarily shorter)
					if(in_array($neighbour,static::$_toVisit)) {
						// This is the current shortest distance between the neighbour in the loop and the source
						$neighbourDistSource = $neighbour->getDistToSource();

						// This is the current shortest distance between the current node and the
						// source + the distance between the current node and the neighbour
						$neighbourDistCurrent = ($node->getDistToSource() + $node->getNeighbourDist($neighbour));

						// Checking if it is faster to go to the neighbour by the current node (or if the neighbour hasn't been reached yet (IMPOSSIBLE_DIST))
						if($neighbourDistSource == DijkstraNode::IMPOSSIBLE_DIST OR ($neighbourDistCurrent < $neighbourDistSource)) {
							// Set the new shortest distance between the neighbour and the source
							$neighbour->setDistToSource($neighbourDistCurrent);
							// Set the new predecessor of the neighbour in the path to the source
							static::$_preds[$neighbour->getId()] = $node->getId();
						}

					}
				}

			}

			// Add the current node to the visited nodes
			static::$_visited[] = $node;
		}

		$arrNodesDistsToSource = array();

		// Setting an array having key => nodeId, value => min distance to this node from the source
		foreach(static::$_visited as $node) {
			$arrNodesDistsToSource[$node->getId()] = $node->getDistToSource();
		}

		$ret = array(
			'paths' => static::$_preds, // key => node id, value => predecessor (node id) in the shortest path to the source
			'pathsCosts' => $arrNodesDistsToSource // Look at the last loop
		);

		return $ret;
	}

	private static function _init() {
		// Setting all predecessors of the nodes to null because default, they are unreachable
		foreach(static::$_toVisit as $node) {
			static::$_preds[$node->getId()] = null;
		}

		// Setting the distance between the source and itself to 0 to get 
		// a starting point in the algorithm (see sortNodes)
		static::$_source->setDistToSource(0);
	}

	/**
	* This sort the nodes to visit by their current shortest distances to the source
	* This method pay attention to IMPOSSIBLE_DIST which is set to -1
	*/
	private static function _sortNodes() {
		usort(static::$_toVisit,
			function ($a,$b) {
				$aDistToSource = $a->getDistToSource();
				$bDistToSource = $b->getDistToSource();

				if($aDistToSource == DijkstraNode::IMPOSSIBLE_DIST AND $bDistToSource == DijkstraNode::IMPOSSIBLE_DIST) {
					return 0;
				}
				elseif($aDistToSource == DijkstraNode::IMPOSSIBLE_DIST) {
					return 1;
				}
				elseif($bDistToSource == DijkstraNode::IMPOSSIBLE_DIST) {
					return -1;
				}
				elseif($aDistToSource > $bDistToSource) {
					return 1;
				}
				else if($aDistToSource < $bDistToSource) {
					return -1;
				}
				else {
					return 0;
				}
			}
		);
	}
}

$nodeA = new DijkstraNode('A');
$nodeB = new DijkstraNode('B');
$nodeC = new DijkstraNode('C');
$nodeD = new DijkstraNode('D');
$nodeE = new DijkstraNode('E');
$nodeF = new DijkstraNode('F');

$nodeA->addNeighbour($nodeB,1);

$nodeB->addNeighbour($nodeE,2);

$nodeC->addNeighbour($nodeB,2,false); // That third argument set the reciprocity to tell that you can only go from C to B and not from B to C
$nodeC->addNeighbour($nodeF,1);

$nodeD->addNeighbour($nodeE,4);

$nodeE->addNeighbour($nodeF,3);

$nodes = DijkstraNode::getNodes();

$dijkstra = Dijkstra::findRoute($nodes,$nodeA);

// This contains an array which has as key the id of the nodes and for value 
// the predecessor of the node in the shortest path to the source
$paths = $dijkstra['paths'];

// This contains the shortest path cost foreach node (indexed by node id)
$pathsCosts = $dijkstra['pathsCosts'];

foreach($paths as $nodeId => $nodePred) {
	$pred = $nodePred;

	$cPath = array($nodeId);

	while($pred) {
		$cPath[] = $pred;
		$pred = $paths[$pred];
	}

	$cPath = array_reverse($cPath);

	echo 'Shortest path to '.$nodeId.' : '.implode('-',$cPath).' ('.$pathsCosts[$nodeId].') <br /><br />';
}

/*

Shortest path to A : A (0)

Shortest path to B : A-B (1)

Shortest path to C : A-B-E-F-C (7)

Shortest path to D : A-B-E-D (7)

Shortest path to E : A-B-E (3)

Shortest path to F : A-B-E-F (6)

*/
?>

 

It seems it take route input at code , what i need is take input from MYSQL database and take output to MYSQL database

 

I modify it but it is always give error

 

i want these inputs to be quiried from database

$nodeA = new DijkstraNode('A');
$nodeB = new DijkstraNode('B');
$nodeC = new DijkstraNode('C');
$nodeD = new DijkstraNode('D');
$nodeE = new DijkstraNode('E');
$nodeF = new DijkstraNode('F');

$nodeA->addNeighbour($nodeB,1);

$nodeB->addNeighbour($nodeE,2);

$nodeC->addNeighbour($nodeB,2,false); // That third argument set the reciprocity to tell that you can only go from C to B and not from B to C
$nodeC->addNeighbour($nodeF,1);

$nodeD->addNeighbour($nodeE,4);

$nodeE->addNeighbour($nodeF,3);

 

But it always give me error in findroute() function

 

Any help ??

[engahmed]

Please Help