7 Replies - 8510 Views - Last Post: 25 July 2011 - 02:48 PM Rate Topic: -----

#1 Wild_Rose  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 39
  • Joined: 13-April 07

Could anyone help me with this Dijkstra's algorithm?

Posted 02 August 2007 - 07:55 AM

Hello everyone!
I want to use Dijkstra's shortest route algorithm in PHP! I use 3 php pages, one is map.php which has an image of a map with hotspots (the user can only pick 2 places), the second one is dijkstra.php which has the algorithm in php and the third one is calPath.php which executes the procedure.

Please take a look:
map.php
<html>
<head>
<title>Find shortest route!</title>

<script>

function clickMap(classID)
{
	if (document.form1.fromClass.value.length == 0)
	{
		document.form1.fromClass.value = classID;
	}
	else
	{
		document.form1.toClass.value = classID;
	}
}

</script>
</head>
<body>

<img src="teiMap.jpg"  usemap="#routes" border="0">

<MAP name="routes" >
	<AREA SHAPE="rect" COORDS="225,50, 300, 100"  href="java script:clickMap('1');" class="mymap" >
	<AREA SHAPE="rect" COORDS="400,400,500,500" href="java script:clickMap('3');"  class="mymap" >
</MAP>

<br><br>
<form name="form1" action="calPath.php" method="post">

From : 
<input type="text" name="fromClass"/>

<br>
To :
<input type="text" name="toClass"/>
<br>
<input name=b1 type=submit value="Enter!">

</form>

<br></body></html>



dijkstra.php

<?php
class Dijkstra {
 
	var $visited = array();
	var $distance = array();
	var $previousNode = array();
	var $startnode =null;
	var $map = array();
	var $infiniteDistance = 0;
	var $numberOfNodes = 0;
	var $bestPath = 0;
	var $matrixWidth = 0;
 
	function Dijkstra(&$ourMap, $infiniteDistance) {
		$this -> infiniteDistance = $infiniteDistance;
		$this -> map = &$ourMap;
		$this -> numberOfNodes = count($ourMap);
		$this -> bestPath = 0;
	}
 
	function findShortestPath($start,$to) {
		$this -> startnode = $start;
		for ($i=0;$i<$this -> numberOfNodes;$i++) {
			if ($i == $this -> startnode) {
				$this -> visited[$i] = true;
				$this -> distance[$i] = 0;
			} else {
				$this -> visited[$i] = false;
				$this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) 
					? $this -> map[$this -> startnode][$i] 
					: $this -> infiniteDistance;
			}
			$this -> previousNode[$i] = $this -> startnode;
		}
		
		$maxTries = $this -> numberOfNodes;
		$tries = 0;
		while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {			
			$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false,true));
			if($to !== null && $this -> bestPath === $to) {
				break;
			}
			$this -> updateDistanceAndPrevious($this -> bestPath);			
			$this -> visited[$this -> bestPath] = true;
			$tries++;
		}
	}
 
	function findBestPath($ourDistance, $ourNodesLeft) {
		$bestPath = $this -> infiniteDistance;
		$bestNode = 0;
		for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
			if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
				$bestPath = $ourDistance[$ourNodesLeft[$i]];
				$bestNode = $ourNodesLeft[$i];
			}
		}
		return $bestNode;
	}
 
	function updateDistanceAndPrevious($obp) {		
		for ($i=0;$i<$this -> numberOfNodes;$i++) {
			if( 	(isset($this->map[$obp][$i])) 
				&&	(!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 ))	
				&&	(($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i])
			) 	
			{
					$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
					$this -> previousNode[$i] = $obp;
			}
		}
	}
 
	function printMap(&$map) {
		$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
		$foo = '';
		for($i=0,$im=count($map);$i<$im;$i++) {
			for ($k=0,$m=$im;$k<$m;$k++) {
				$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
			}
			$foo.= "\n";
		}
		return $foo;
	}
 
	function getResults($to) {
		$ourShortestPath = array();
		$foo = '';
		for ($i = 0; $i < $this -> numberOfNodes; $i++) {
			if($to !== null && $to !== $i) {
				continue;
			}
			$ourShortestPath[$i] = array();
			$endNode = null;
			$currNode = $i;
			$ourShortestPath[$i][] = $i;
			while ($endNode === null || $endNode != $this -> startnode) {
				$ourShortestPath[$i][] = $this -> previousNode[$currNode];
				$endNode = $this -> previousNode[$currNode];
				$currNode = $this -> previousNode[$currNode];
			}
			$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
			if ($to === null || $to === $i) {
			if($this -> distance[$i] >= $this -> infiniteDistance) {
				$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
			} else {
				$foo .= sprintf(' From %d => to  %d = %d (meters) <br> destinations [%d]: Follow the route to the classes (%s).'."\n" ,
						$this -> startnode,$i,$this -> distance[$i],
						count($ourShortestPath[$i]),
						implode('-',$ourShortestPath[$i]));
			}
			$foo .= str_repeat('-',20) . "\n";
				if ($to === $i) {
					break;
				}
			}
		}
		return $foo;
	}
} // end class 
?>



calPath.php
<?php
 
include("dijkstra.php");


// I is the infinite distance.
define('I',1000);
 
// Size of the matrix
$matrixWidth = 4;
 
// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
	array(1,3,7),
	array(1,2,1),
	array(2,3,1),
	array(3,4,2)
);
 
$ourMap = array();
 
 
// Read in the points and push them into the map
 
for ($i=0,$m=count($points); $i<$m; $i++) {
	$x = $points[$i][0];
	$y = $points[$i][1];
	$c = $points[$i][2];
	$ourMap[$x][$y] = $c;
	$ourMap[$y][$x] = $c;
}
 
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
 
for ($i=0; $i < $matrixWidth; $i++) {
	for ($k=0; $k < $matrixWidth; $k++) {
		if ($i == $k) $ourMap[$i][$k] = 0;
	}
}
 
 
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
 
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
$fromClass = $_POST['fromClass'];
$toClass = $_POST['toClass'];

$dijkstra->findShortestPath($fromClass, $toClass); 
 
// Display the results
 
echo '<pre>';
//echo "the map looks like:\n\n";
//echo $dijkstra -> printMap($ourMap);
echo "\n\n the shortest route from class  ".$fromClass." to ".$toClass." is  :\n";
echo $dijkstra -> getResults((int)$toClass);
echo '</pre>';

 
?>


but when I run it (I pick the destination from 1 to 3) I get a warning
Warning: Wrong parameter count for array_keys() in c:\program files\easyphp1-8\www\teiguide\dijkstra.php on line 39

and it says that the shortest route from 1 to 3 is 1 to 3 (which should say is 1 to 2 to 3 instead!)

any ideas???????

thanks a LOT for you time...

This post has been edited by hotsnoj: 02 August 2007 - 10:37 AM


Is This A Good Question/Topic? 1
  • +

Replies To: Could anyone help me with this Dijkstra's algorithm?

#2 snoj  Icon User is offline

  • Married Life
  • member icon

Reputation: 84
  • View blog
  • Posts: 3,564
  • Joined: 31-March 03

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 02 August 2007 - 10:12 AM

Liar! You made me think that you solved Dijkstra's algorithm in PHP.

Learn how to use question marks.
Was This Post Helpful? 0
  • +
  • -

#3 Wild_Rose  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 39
  • Joined: 13-April 07

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 02 August 2007 - 10:59 AM

LOL, sorry!
I used this guide to make it http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP

This post has been edited by Wild_Rose: 02 August 2007 - 11:12 AM

Was This Post Helpful? 0
  • +
  • -

#4 Wild_Rose  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 39
  • Joined: 13-April 07

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 14 September 2007 - 04:50 AM

ha! I made it work, I just deleted one variable that was causing the problem! :D
Was This Post Helpful? 0
  • +
  • -

#5 PennyBoki  Icon User is offline

  • system("revolution");
  • member icon

Reputation: 53
  • View blog
  • Posts: 2,334
  • Joined: 11-December 06

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 14 September 2007 - 04:55 AM

It would be nice of you if you post the solution, so that others will see it :)
Was This Post Helpful? 0
  • +
  • -

#6 Wild_Rose  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 39
  • Joined: 13-April 07

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 15 September 2007 - 02:00 AM

Of course!

First of all, I have created a mapwith hotspots where the visitor can click on them (I did that with javascript.

The dijkstra.php code is the following:
<?php
class Dijkstra {
 
	var $visited = array();
	var $distance = array();
	var $previousNode = array();
	var $startnode =null;
	var $map = array();
	var $infiniteDistance = 0;
	var $numberOfNodes = 0;
	var $bestPath = 0;
	var $matrixWidth = 0;
 
	function Dijkstra(&$ourMap, $infiniteDistance) {
		$this -> infiniteDistance = $infiniteDistance;
		$this -> map = &$ourMap;
		$this -> numberOfNodes = count($ourMap);
		$this -> bestPath = 0;
	}
 
	function findShortestPath($start,$to) {
		$this -> startnode = $start;
		for ($i=0;$i<$this -> numberOfNodes;$i++) {
			if ($i == $this -> startnode) {
				$this -> visited[$i] = true;
				$this -> distance[$i] = 0;
			} else {
				$this -> visited[$i] = false;
				$this -> distance[$i] = isset($this -> map[$this -> startnode][$i]) 
					? $this -> map[$this -> startnode][$i] 
					: $this -> infiniteDistance;
			}
			$this -> previousNode[$i] = $this -> startnode;
		}
		
		$maxTries = $this -> numberOfNodes;
		$tries = 0;
		while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {			
			$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false));
			if($to !== null && $this -> bestPath === $to) {
				break;
			}
			$this -> updateDistanceAndPrevious($this -> bestPath);			
			$this -> visited[$this -> bestPath] = true;
			$tries++;
		}
	}
 
	function findBestPath($ourDistance, $ourNodesLeft) {
		$bestPath = $this -> infiniteDistance;
		$bestNode = 0;
		for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
			if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
				$bestPath = $ourDistance[$ourNodesLeft[$i]];
				$bestNode = $ourNodesLeft[$i];
			}
		}
		return $bestNode;
	}
 
	function updateDistanceAndPrevious($obp) {		
		for ($i=0;$i<$this -> numberOfNodes;$i++) {
			if( 	(isset($this->map[$obp][$i])) 
				&&	(!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 ))	
				&&	(($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i])
			) 	
			{
					$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
					$this -> previousNode[$i] = $obp;
			}
		}
	}
 
	function printMap(&$map) {
		$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
		$foo = '';
		for($i=0,$im=count($map);$i<$im;$i++) {
			for ($k=0,$m=$im;$k<$m;$k++) {
				$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
			}
			$foo.= "\n";
		}
		return $foo;
	}
 
	function getResults($to) {
		$ourShortestPath = array();
		$foo = '';
		for ($i = 0; $i < $this -> numberOfNodes; $i++) {
			if($to !== null && $to !== $i) {
				continue;
			}
			$ourShortestPath[$i] = array();
			$endNode = null;
			$currNode = $i;
			$ourShortestPath[$i][] = $i;
			while ($endNode === null || $endNode != $this -> startnode) {
				$ourShortestPath[$i][] = $this -> previousNode[$currNode];
				$endNode = $this -> previousNode[$currNode];
				$currNode = $this -> previousNode[$currNode];
			}
			$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
			if ($to === null || $to === $i) {
			if($this -> distance[$i] >= $this -> infiniteDistance) {
				$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
			} else {
				$foo .= sprintf(' from %d => to  %d = %d (distance) <br> Number of sports : %d: 
		Follow the route (%s).'."\n" ,
						$this -> startnode,$i,$this -> distance[$i],
						count($ourShortestPath[$i]),
						implode('-',$ourShortestPath[$i]));
			}
			$foo .= str_repeat('-',20) . "\n";
				if ($to === $i) {
					break;
				}
			}
		}
		return $foo;
	}
} // end class 
?>



and the calPath.php file is
<?php
 
include("dijkstra.php");
include_once('theme.php');

pageheader("ii_icon");

// I is the infinite distance.
define('I',1000);
 
// Size of the matrix
$matrixWidth = 69;
 
// $points is an array in the following format: (router1,router2,distance-between-them)
$points = array(
	array(0,1,5),
	array(1,2,2),
	array(1,8,2),
	array(1,9,2),
	array(1,10,2),
	array(2,3,1),
	array(2,7,3),
	array(3,4,1),
	array(3,5,1),
	array(3,7,1),
	array(4,5,1),
	array(4,6,1),
	array(4,7,2),
	array(5,6,1),
	array(5,13,3),
	array(6,7,3),
	array(6,14,1),
	array(7,8,1),
  array(7,10,3),
	array(7,11,1),
	array(7,12,2),
	array(7,14,2),
	array(8,9,3),
	array(8,10,2),
	array(8,11,3),
	array(9,10,2),
	array(9,15,1),
	array(9,17,2),
	array(10,11,1),
	array(10,17,1),
	array(10,18,1),
	array(11,12,1),
	array(11,18,2),
	array(12,13,1),
	array(12,18,1),
	array(12,19,1),
	array(12,20,1),
	array(14,22,2),
	array(15,16,1),
	array(16,17,2),
	array(16,21,1),
	array(17,18,1),
	array(17,21,1),
	array(17,25,2),
	array(18,19,1),
	array(18,21,1),
	array(19,20,1),
	array(19,21,1),
	array(19,22,2),
	array(19,23,1),
	array(21,23,3),
	array(21,24,2),
	array(21,25,1),
	array(22,23,1),
	array(23,24,2),
	array(24,25,3),
	array(24,26,2),
	array(25,26,2),
	array(25,27,1),
	array(26,27,3),
	array(26,28,1),
	array(27,28,2),
	array(27,29,1),
	array(28,29,3),
	array(28,30,2),
	array(29,30,3),
	array(30,31,2),
	array(31,32,1)
	
);


$ourMap = array();
 
 
// Read in the points and push them into the map
 
for ($i=0,$m=count($points); $i<$m; $i++) {
	$x = $points[$i][0];
	$y = $points[$i][1];
	$c = $points[$i][2];
	$ourMap[$x][$y] = $c;
	$ourMap[$y][$x] = $c;
}
 
// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.
 
for ($i=0; $i < $matrixWidth; $i++) {
	for ($k=0; $k < $matrixWidth; $k++) {
		if ($i == $k) $ourMap[$i][$k] = 0;
	}
}
 
 
// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);
 
// $dijkstra->findShortestPath(0,13); to find only path from field 0 to field 13...
if (!isset($_POST['fromClassID']))
{
  $fromClassID = $_POST['fromSelected'];
  $fromClass = $_POST['fromSelectedClass'];
}
else
{
  $fromClassID = $_POST['fromClassID'];
  $fromClass = $_POST['fromClass'];
}


if (!isset($_POST['toClassID']))
{
  $toClassID = $_POST['toSelected'];
  $toClass = $_POST['toSelectedClass'];
}
else
{
  $toClassID = $_POST['toClassID'];
  $toClass = $_POST['toClass'];
}


$dijkstra->findShortestPath($fromClassID, $toClassID); 
 
// Display the results
 
   pageheader("ii_icon");
   
echo '<pre>';

//echo "the map looks like:\n\n";
//echo $dijkstra -> printMap($ourMap);
echo "\n\n The shortest route from place  <b>".$fromClass."</b> (".$fromClassID.") <br> "
	  ." to <b>".$toClass."</b> (".$toClassID.") is the following  :  <br>\n";
echo $dijkstra -> getResults((int)$toClassID);
echo '</pre>';

echo "<img src=\"maps/map_routes.jpg\">";

pagefooter();
?>



:D

btw If anyone has any idea of how to draw the actual route on the map (with javascript or flash) please let me know!
Was This Post Helpful? 1
  • +
  • -

#7 Kartik.Sulakhe  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 24-July 11

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 25 July 2011 - 02:47 PM

Hey, what wrong and where is my clarifications.
I can't see it's going away after sometime, WHY? PLEASE......

This post has been edited by Kartik.Sulakhe: 25 July 2011 - 02:48 PM

Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10772
  • View blog
  • Posts: 40,122
  • Joined: 27-December 08

Re: Could anyone help me with this Dijkstra's algorithm?

Posted 25 July 2011 - 02:48 PM

This thread is four years old. As the OP hasn't been active since 2008, I don't think he or she can clarify much. Please avoid necroposting.

Topic closed.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1