Jump to content

Dijkstra algorithm problem


engahmed

Recommended Posts

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 - hide@address.com
*/

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 - hide@address.com
*/
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 ??

Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.