Hi:
I used the code below on my Windows 2000 PHP 4.0 but when i sent to my Linux PHP 4.19 it doesn´t work. (undefined offset in both cases, but at first it gave the result properly). help!! tanx Santiago:
BEGIN HERE
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.
<?php
$neighbors[A] = array(B => 2, D => 3);
$neighbors = 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;
reset($neighbors[$closest]);
while(list($vertex, $distance) = each($neighbors[$closest])) {
if ($marked[$vertex])
continue;
$dist = $paths[$closest][0] + $distance;
if (!isset($paths[$vertex]) || ($dist < $paths[$vertex][0])) {
$paths[$vertex] = $paths[$closest];
$paths[$vertex][] = $closest;
$paths[$vertex][0] = $dist;
}
}
unset($closest);
reset ($paths);
while(list($vertex, $path) = each($paths)) {
if ($marked[$vertex])
continue;
$distance = $path[0];
if (($distance < $min) || !isset($closest)) {
$min = $distance;
$closest = $vertex;
}
}
}
return $paths;
}
$paths = dijkstra($neighbors, "A");
while(list($vertex, $path) = each($paths))
echo "$vertex: ", implode(", ", $path), "\n";
?>
If you run this you get
B: 2
D: 3
C: 3, B
E: 5, D
F: 6, D, E
This means that we have the following paths starting in A
distance path
2 A-B
3 A-D
3 A-B-C
5 A-D-E
6 A-D-E-F
Stig
