also erstmal zum algorithmus wie er implementiert gehört:
jetzt musst du nur noch überlegen, wie du dem ding die datenbank-daten ordentlich konvertierst, um den dijkstra-algorithmus zum laufen zu bekommen.
PHP-Code:
<?php
/**
* implementing dijkstra's shortes path algorithm in php.
* @author axo
* @access public
* @see [url]http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm[/url]
*
*/
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;
/**
* constructor.
* @param $ourMap array
* @param $infiniteDistance integer
* @access public
*/
function Dijkstra(&$ourMap, $infiniteDistance) {
$this -> infiniteDistance = $infiniteDistance;
$this -> map = &$ourMap;
$this -> numberOfNodes = count($ourMap);
$this -> bestPath = 0;
}
/**
* finds the shortest path from $start to $to .
* if $to is not set or null, all paths are calculated.
* @param $start integer
* @param $to integer
* @return void
* @access public
*/
function findShortestPath($start,$to = null) {
$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] = $this -> map[$this -> startnode][$i];
}
$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++;
}
}
/**
* finds the best path
* @access private
*
*/
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;
}
/**
* @access private
*/
function updateDistanceAndPrevious($ourBestPath) {
for ($i=0;$i<$this -> numberOfNodes;$i++) {
if((!($this -> map[$ourBestPath][$i] == $this -> infiniteDistance) || ($this -> map[$ourBestPath][$i] == 0))
&& (($this -> distance[$ourBestPath] + $this -> map[$ourBestPath][$i]) < $this -> distance[$i])) {
$this -> distance[$i] = $this -> distance[$ourBestPath] + $this -> map[$ourBestPath][$i];
$this -> previousNode[$i] = $ourBestPath;
}
}
}
/**
* prints a map.
* @param $map array
* @return string
* @access public
*/
function printMap(&$map) {
$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
$foo = '';
for($i=0,$im=count($map);$i<$im;$i++) {
for ($k=0,$m=count($map[$i]);$k<$m;$k++) {
$foo.= sprintf($placeholder,$map[$i][$k]);
}
$foo.= "\n";
}
return $foo;
}
/**
* shows the result.
* @return string
* @access public
*/
function getResults($to = null) {
$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('%d => %d = %d [%d]: (%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;
}
}
define('I',1000);
$points = array(
array(0,1,4),
array(0,2,I),
array(1,2,5),
array(1,3,5),
array(2,3,5),
array(3,4,5),
array(4,5,5),
array(4,5,5),
array(2,10,30),
array(2,11,40),
array(5,19,20),
array(10,11,20),
array(12,13,20),
array(5,6,80),
array(5,7,90),
array(8,0,90),
array(7,10,40),
array(3,12,120),
array(7,9,30),
array(14,5,39),
array(15,16,20),
array(17,16,40),
array(18,15,20),
array(19,0,20),
array(19,18,60),
array(28,19,120),
array(29,19,299),
array(5,27,29),
array(9,20,60),
array(9,29,50),
array(17,22,50),
array(18,23,40),
array(18,24,20),
array(18,25,29),
array(18,26,20),
array(26,21,20),
);
// building the map
$ourMap = array();
$matrixWidth = 30;
for ($i=0;$i<$matrixWidth;$i++) {
for ($k=0;$k<$matrixWidth;$k++) {
$ourMap[$i][$k] = ($i == $k) ? 0 : I;
if ($i == $k+1 ) {
$ourMap[$i][$k] = 10;
}
if($k == $i+1) {
$ourMap[$i][$k] = 10;
}
}
}
for ($i=0,$m=count($points);$i<$m;$i++) {
$x = $points[$i][0];
$y = $points[$i][1];
$c = $points[$i][2];
assert($x != $y);
$ourMap[$x][$y] = $c;
$ourMap[$y][$x] = $c;
}
$dijkstra = new Dijkstra($ourMap, I);
$dijkstra -> findShortestPath(0,22);
echo '<pre>';
echo "the map looks like:\n\n";
echo $dijkstra -> printMap($ourMap);
echo "\n\nthe shortest path from 0 to 22:\n";
echo $dijkstra -> getResults(22);
echo '</pre>';
?>
Kommentar