I am using dijkstra's algorithm to try to gather fake street names and find the shortest path. However, I can only get numbers to work instead of strings... The example of my results is below.
Results:
The shortest route from 0 to 1 is :
From Street 0 to Street 1 = 5 (miles)
Number of streets: 2
Directions: (Street 0-1).
I want it to change to something like...
The shortest route from George St to Alice St is:
From George St to Alice St = 5 (miles)
Number of Streets: 2
Directions: (George St to Alice St).
I have been playing around with my CalPath.php for the past few weeks trying to change the ints to strings inside of my $points array, but my results have been unsuccessful. Like for my first array, I change (0,1,5) to ('George St','Alice St',5).
If someone can guide on the right track, I will appreciate it.
CalPath.php - stores ints but I want to store fake roads instead and present accurate results
<?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(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...
$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 ".$fromClass." to ".$toClass." is :\n";
echo $dijkstra -> getResults((int)$toClass);
echo '</pre>';
?>dijkstra.php - gets the shortest path
<?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 Street %d to Street %d. \n",$this -> startnode,$i);
} else {
$foo .= sprintf(' From Street %d to Street %d = %d (miles) <br> Number of streets: %d <br> Directions: (Street %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
?>map.html - allows you to enter the source and destination which currently allows you to enter ints.
<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>
<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>