Dijkstras Algorithm Shortes Path

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

)