# Could anyone help me with this Dijkstra's algorithm?

Page 1 of 1

## 7 Replies - 8590 Views - Last Post: 25 July 2011 - 02:48 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=31153&amp;s=6bd4c842a178c201ab44cacc9ef3826f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Wild_Rose

Reputation: 2
• 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.

map.php
```<html>
<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>
<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

• Married Life

Reputation: 84
• 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.

### #3 Wild_Rose

Reputation: 2
• 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

### #4 Wild_Rose

Reputation: 2
• 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!

### #5 PennyBoki

• system("revolution");

Reputation: 53
• Posts: 2,335
• 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

### #6 Wild_Rose

Reputation: 2
• 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:
\$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');

// 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

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();
?>

```

btw If anyone has any idea of how to draw the actual route on the map (with javascript or flash) please let me know!

### #7 Kartik.Sulakhe

Reputation: 0
• 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

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11312
• Posts: 42,605
• 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.