Route Planner

elenaki.xs · August 19, 2009

Hi, I'm trying to built a route planner to put in my website so I found something similar to what I need (based in http://en.giswiki.net/wiki/Dijkstra's_algorithm).

The code consists of three .php files; the map.php which includes the form for the application, the dijkstra.php which contains the variable and function definitions and calPath.php which contains the possible routes. the codes are as follows:

map.php

<html>
<head>
<title>Find shortest route!</title>

<script type="text/javascript">

function clickMap(classID) // this function says if its the first click on the map identify as 'from' attribute, if second or more identify as 'to' attribute.
{
    if (document.form1.fromClass.value.length == 0)
    {
        document.form1.fromClass.value = classID;
    }
    else
    {
        document.form1.toClass.value = classID;
    }
}

function writeText(txt) //this function says if the user passes the mouse over the point a defined text appears corresponding to the clickable point. 
{
document.getElementById("desc").innerHTML=txt;
}

</script>
</head>
<body>

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

<MAP name="routes" >
    <AREA SHAPE="circle" COORDS="30,58,10"  onMouseOver="writeText('1')" href="java script:clickMap('1');" class="mymap" />
    <AREA SHAPE="circle" COORDS="80,58,10"  onMouseOver="writeText('2')" href="java script:clickMap('2');" class="mymap" />
    <AREA SHAPE="circle" COORDS="120,58,10" onMouseOver="writeText('3')" href="java script:clickMap('3');"  class="mymap" />
</MAP>

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

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

<br />
To :
<input type="text" name="destination"/>
<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)
// this array defines the routes
$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

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'];  // taken from map.php
$toClass = $_POST['toClass'];		// taken from map.php

$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>';

?>

The code is not the same as the original I found, I have made some changes to fit my needs but I cannot find how to do one thing: I want the routes to be defined with letters (words) and not numbers (in calPath.php) but I can find what to change in order to let me do this (currently it messes up the results if i change it to letters). I want the user to be able to ask what is the shortest/fastest way from A to B. I read another similar post but didnt held me.

Thank you

elenaki.xs

ignace · August 19, 2009

Store the name of a point in your database along with it's coördinates

elenaki.xs · August 20, 2009

let me see if I got this right;

I should build a table in my db i.e. 'points' which would include;

point_id, point_name, point_coordinates ->

1, A, 4*5

2, B, 2*4 etc?

If I got it right, what else could I put instead of coordinates? As I dont want to give coordinates for each place but distance in terms of travelling time between them (I want to be able to define the distance in the code, like it is currently).

Also, where in the code do I put the reference of the db so that the array identifies it?

Thanks very much for the quick reply,

elenaki.xs

Sign In

Route Planner

Recommended Posts

elenaki.xs

Link to comment

Share on other sites

ignace

Link to comment

Share on other sites

elenaki.xs

Link to comment

Share on other sites

Join the conversation

Browse

Activity

Important Information