PHPBuilder - Dijkstras Algorithm Shortes Path

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
)

)

```

Comment and Contribute

Your comment has been submitted and is pending approval.

Author:
Wouter

Comment:

Comment:

(Maximum characters: 1200). You have characters left.