ここ2年ほど、 AtCoder という競技プログラミングを楽しんでいます。
おもに PHP を使っているのですが、インターネット上に、なかなかちょうどよい記事を見つけられないため、過去の自分が悩んだところを、まとめて置きたいと思います。

以前、 Union Find について紹介したことがあります が、今回は、 Dijkstra 法についてまとめます。

Dijkstra 法とは

Dijkstra と書かれても、そもそも読み方が難しいです。
エドガー・ダイクストラ（ Dijkstra ）さんという、オランダのコンピュータ科学者が発見したアルゴリズムが、ダイクストラ法（だいくすとらほう、 Dijkstra’s algorithm）です。

辺でつながったグラフ上のある点から、他の到達可能なすべての点までの、最短距離を効率よく求められます。

実用上のことはあまり詳しくないのですが、たとえば、 Yahoo 路線情報のような路線検索において、出発駅から到着駅までの経路がいくつかあるときに、乗車時間の最短時間や、運賃の最安値を計算をしたい場合に使えそうです。

今回は、これを PHP で実装してみます。

実装したものがこちら

<?php
function dijkstra(array $graph, int $n, int $start) {
        $dist = array_fill(0, $n, PHP_INT_MAX);
        $dist[$start] = 0;
        $que = new SplPriorityQueue();
        $que->insert([0, $start], 0);
        while(!$que->isEmpty()) {
                [$d, $v] = $que->extract();
                if($d > $dist[$v]) {
                        continue;
                }
                foreach($graph[$v] as $u => $weight) {
                        $newd = $d + $weight;
                        if($dist[$u] > $newd) {
                                $dist[$u] = $newd;
                                $que->insert([$newd, $u], -$newd);
                        }
                }
        }
        return $dist;
}

// 使い方：
$g = [];
$g[0][1] = 1;
$g[1][0] = 1;
$g[0][2] = 6;
$g[2][0] = 6;
$g[1][2] = 2;
$g[2][1] = 2;
$dist = dijkstra($g, count($g), 0); // 0からの距離
echo implode(' ', $dist).PHP_EOL;

簡単に解説します。

元となるデータ構造は、優先度付きキューです。
（優先度付きキューについては、 以前 Qiita に記事を書いたことがある ので、興味のある方は読んでみてください）

スタートとなる点から、辺でつながった各点までの重みを、優先度付きキューで管理して、軽い順に並べます。
新しい到達点が見つかるたびに、軽い順で並び直されるため、常にその時点で最も軽い辺を選び続けることができます。

そして、過去に到達した重みよりも、軽い到達方法が見つかれば、順次更新されていきます。

過去に探索した、それよりもより重い重みによる到達方法も、キューには装填済みですが、優先度付きキューにより後回しにされるため、結果的に無駄な計算が無視されるというわけです。

その時点で候補となる到達点について、重みの小さい順に並び替え続けるため、常に最短の経路を検討し続けることが可能となります。

ダイクストラ法の利用上の注意点

上記解説の通り、ダイクストラ法は、過去に到達した重さよりも軽い点が見つかれば、それを上書きするようになっています。
このことは逆に言えば、もし辺の重みにマイナスがあると、過去に確定した点の到達を上書きしてしまい、再計算が必要になるということです。
これにより、無駄な再計算がたくさん出てくる事態になりえますし、最悪の場合、サイクルのたびにどんどん軽くなっていって、無限ループになるおそれもあります。

よく、ダイクストラ法は辺の重みがすべて非負（0以上）でなければならないと言われるのは、このような理由によるものです。

計算量と実用度

頂点数を V, 辺の数を E とするとき、およその計算量は O(ElogV) です。
（logV の部分は、優先度付きキューの並び替え時間です。実際は、 class の呼び出しなどのオーバーヘッドがあるため、理論通りの時間計算量ではないです）

およそ 10の5乗（10万）くらいの頂点を持つグラフであれば、1000ミリ秒程度で計算が終わることが多いです。
これは、イメージ的には、 10万個の駅がある路線図に対して、ある駅から他のすべての駅までの到達時間を調べるのに、1秒程度でできてしまうことを意味します。

十分高速ですし、実用的なアルゴリズムと言えそうです。