Snippets Algorithms
Algorithms
Dijkstras Algorithm Shortes Path
by: Wouter
|
March 4, 2006
Version: 1.1
Type: Full Script
Category: Algorithms
License: GNU General Public License
Description: This function allows to trace the shortest path beetwen nodes and traces the route, for example on a map. I found on a forum and i think its very good, altougth i think it doesnt works properly on >PHP 4.0.
> I'm wondering has anyone made a some kind of "program" (with PHP) which finds the shortest way between
two nodes in a node network? The program could also tell the nodes by shortest route and distance.
>
> I have heard something about Dijkstra's algorithm...
>
> Can anyone help me? or the best, can anyone send sources?
The following should work I think, let me show an example:
B-------C
/ \ 1 \
2 / \ \5
/ \ \
A \4 F G
\ \ /
3 \ \ /1
\ \ /
D-------E
2
This graph can be represented by listing the neighbors for each
vertex, like below, and then calling the function dijkstra.
NOTE: this version DOES work for PHP 5.
<?php
/* the neighbors array */
$neighbors['A'] = array('B' => 2, 'D' => 3);
$neighbors['B'] = array('A' => 2, 'C' => 1, 'E' => 4);
$neighbors['C'] = array('B' => 1, 'F' => 5);
$neighbors['D'] = array('A' => 3, 'E' => 2);
$neighbors['E'] = array('D' => 2, 'B' => 4, 'F' => 1);
$neighbors['F'] = array('C' => 5, 'E' => 1);
function dijkstra($neighbors, $start) {
$closest = $start;
while (isset($closest)) {
$marked[$closest] = 1;
/* loop through each neighbor for this $closest node and
* and store the distance and route in an array */
foreach ($neighbors[$closest] as $vertex => $distance) {
/* if we already have the route and distance, skip */
if (isset($marked[$vertex]))
continue;
/* distance from $closest to $vertex */
$dist = (isset($paths[$closest][0]) ? $paths[$closest][0] : 0) + $distance;
/* if we dont have a path to $vertex yet, create it.
* If this distance is shorter, override the existing one */
if (!isset($paths[$vertex]) || ($dist < $paths[$vertex][0])) {
if (isset($paths[$closest])) {
$paths[$vertex]= $paths[$closest];
}
$paths[$vertex][] = $closest;
$paths[$vertex][0] = $dist;
}
}
unset($closest);
/* Find the next node we should create a path for */
foreach ($paths as $vertex => $path) {
if (isset($marked[$vertex]))
continue;
$distance = $path[0];
if ((!isset($min) || $distance < $min) || !isset($closest)) {
$min = $distance;
$closest = $vertex;
}
}
}
return $paths;
}
$paths = dijkstra($neighbors, 'A');
print_r($paths);
?>
If you run this, you get this:
Array
(
[B] => Array
(
[0] => 2
)
[D] => Array
(
[0] => 3
)
[C] => Array
(
[0] => 3
[1] => B
)
[E] => Array
(
[0] => 5
[1] => D
)
[F] => Array
(
[0] => 6
[1] => D
[2] => E
)
)
PHPBuilder
Policies
PHP Developer
Topics
PHP Developer
Resources
PHP Developer
References
