ダイクストラ法をWikipedia(英語)の記述に100%沿ってPHPで書いてみた

教育用の覚書。最短経路問題のアルゴリズムとして有名なダイクストラ法(Dijkstra's Algorithm)をDijkstra's algorithm - Wikipediaの記述に忠実に実装をPHPで書いてみた。PHP独特の配列の取扱いや変数の自動アロケーションを使って、原文の記述の順番をまったく崩さずにコードを書いてみた。一応、関数の呼出と探索後の最短経路のピックアップまで書いてあるので、コンプリートコードである。マップのデータはWikipediaのものを起こした。日本語版ダイクストラ法 - Wikipediaのアルゴリズムの概要の記述は「アルゴリズム」にはなっていないので、コードを直接書き下すのには役に立たない。とくに「ビー玉と紐」のたとえはノードチェックのプロセスをわかりにくくしている。やはり日本語版は酷いものが多い。

<?php
//step aux.
// Set the distance of the edges.

    $listDistEdge= array(
       "1"=>array("2"=>7,"3"=>9,"6"=>14)
      ,"2"=>array("1"=>7,"3"=>10,"4"=>15)
      ,"3"=>array("1"=>9,"2"=>10,"4"=>11,"6"=>2)
      ,"4"=>array("2"=>15,"3"=>11,"5"=>6)
      ,"5"=>array("4"=>6,"6"=>9)
      ,"6"=>array("1"=>14,"3"=>2,"5"=>9)
    );

//
// Wikipedia "Dijkstra's algorithm" says...
//
    function dijkstraAlgorithm ($nodeStart ,$listDistEdge) {

step_1:
// Assign to every node a distance value:
// set it to zero for our initial node ... 

      $v["distNode"][$nodeStart]= 0;

//(step 1)
// ... and to infinity for all other nodes.

      foreach ( $listDistEdge as $node => $nodeNext) {
        if ( !isset($v["distNode"][$node]) ) {
          $v["distNode"][$node]= INF;
        }
      }

step_2:
// Mark all nodes as unvisited.

      foreach ( $listDistEdge as $node => $nodeNext) {
        $v["flagVisited"][$node]= 0;
      }

//step aux.
// We also allocate an array for the node data of the optimal path 
// and set it to the initial node data for the initial node record
// (to stop back tracking of nodes at the initial node).

      $v["nodePrev"][$nodeStart]= $nodeStart;

//step aux.
// We will list the unvisited nodes and their distance in this array.

      $v["nodeUnvisited"][$nodeStart]= 0;

//(step 2)
// Set initial node as current.

      $nodeCurr= $nodeStart;

step_3:
// For current node, consider all its unvisited neighbors ...

      foreach ( $listDistEdge[$nodeCurr] as $nodeNext => $distEdge ) {
        if ( $v["flagVisited"][$nodeNext] != 1 ) {

//(step 3)
// ...and calculate their tentative distance (from the initial node).
// For example, if current node (A) has distance of 6,
// and an edge connecting it with another node (B) is 2,
// the distance to B through A will be 6+2=8.

          $distTrial= $v["distNode"][$nodeCurr] + $distEdge;

//(step 3)
// If this distance is less than the previously recorded distance
// (infinity in the beginning, zero for the initial node), ...

          $distPrev= $v["distNode"][$nodeNext];
          if ( $distTrial < $distPrev ) {

//(step 3)
// ... overwrite the distance.

            $v["distNode"][$nodeNext]= $distTrial;
            $v["nodeUnvisited"][$nodeNext]= $distTrial;

//step aux.
// We also overwrite the optimal path data of the neighbour.

            $v["nodePrev"][$nodeNext]= $nodeCurr;

          } // end of if ( $distTrial < $distPrev )

step_4:
// When we are done considering all neighbors of the current node, 
// mark it as visited.

        } // end of if ( $v["flagVisited"][$nodeNext] ...
      } // end of foreach ( $listDistEdge[$nodeCurr] ... 

      $v["flagVisited"][$nodeCurr]= 1;

//(step 4)
// A visited node will not be checked ever again;

      unset($v["nodeUnvisited"][$nodeCurr]);

//(step 4)
// its distance recorded now is final and minimal.

      echo "The minimum distance from $nodeStart to $nodeCurr is "
           .$v["distNode"][$nodeCurr]."<br>\n";

step_5:
// If all nodes have been visited, finish.

      if ( count($v["nodeUnvisited"]) == 0 ) {
        finish:
        return array($v["distNode"],$v["nodePrev"]);
      }

//step 5
// Otherwise, set the unvisited node with the smallest distance
// (from the initial node, considering all nodes in graph)
// as the next "current node" and ...

      else {
        asort($v["nodeUnvisited"]);
        $listNode= array_keys($v["nodeUnvisited"]);
        $nodeCurr= $listNode[0];
      }

//step 5
// ... continue from step 3.

      goto step_3; // PHP 5.3 (or later)

    }// end of function dijkstraAlgorithm ($nodeStart ,$listDistEdge)

function getMinimumPath ($nodeEnd ,$listNodePrev){
  $nodeCurr= $nodeEnd;
  $nodePrev= $listNodePrev[$nodeCurr];
  while ( strcmp($nodeCurr,$nodePrev) ) {
    $backTrack[]= $nodeCurr;
    $nodeCurr= $nodePrev;
    $nodePrev= $listNodePrev[$nodeCurr];
  }
  $backTrack[]= $nodeCurr;
  return $backTrack;
}

function searchPath ($nodeStart ,$nodeEnd ,$listDistEdge) {
  list($listDistNode,$listNodePrev)=
    dijkstraAlgorithm($nodeStart,$listDistEdge);
  return getMinimumPath($nodeEnd,$listNodePrev);
}

$result= searchPath("1","5",$listDistEdge);
var_dump($result);