engahmed Posted February 25, 2012 Share Posted February 25, 2012 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 ?? Quote Link to comment https://forums.phpfreaks.com/topic/257755-dijkstra-algorithm-problem/ Share on other sites More sharing options...
engahmed Posted February 26, 2012 Author Share Posted February 26, 2012 Please Help Quote Link to comment https://forums.phpfreaks.com/topic/257755-dijkstra-algorithm-problem/#findComment-1321402 Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.