Snippets

# Dijkstras Algorithm Shortes Path

**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 ) )