|
i have code like this,,i use php languages..
this for map.php
<title>Find shortest route!
function clickMap(classID) {
if (document.form1.fromClass.value.length == 0)
{ document.form1.fromClass.value = classID; }
else { document.form1.toClass.value = classID; }
}
From :
To :
and this for the dijkstra.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) 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
// I is the infinite distance.
define('I',1000);
$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['fromClass']))
{
$fromClass = $_POST['fromSelected'];
$fromClass1 = $_POST['fromSelectedClass'];
}
else
{
$fromClass = $_POST['fromClass'];
$fromClass1 = $_POST['fromClass'];
}
if (!isset($_POST['toClass']))
{
$toClass = $_POST['toSelected'];
$toClass1 = $_POST['toSelectedClass'];
}
else
{
$toClass = $_POST['toClass'];
$toClass1 = $_POST['toClass'];
}
$dijkstra->findShortestPath($fromClass, $toClass);
// Display the results
// pageheader("ii_icon");
echo '
';
echo "the map looks like:\n\n";
echo $dijkstra -> printMap($ourMap);
echo "\n\n The shortest route from place ".$fromClass1." (".$fromClass.") <br> "
." to ".$toClass1." (".$toClass.") is the following : <br>\n";
echo $dijkstra -> getResults((int)$toClass);
echo '</br></br> ';
echo "";
//pagefooter();
?>
my question is, i have some problem if, i input 1 to 3 the result is from 1-2-3, but dijkstra algoritma i use is single graph,so algorima read same 1-3 with 3-1,,who know which one is wrong?? i want 1-3 not same 3-1
|
|
|
|