ここ2年ほど、 AtCoder という競技プログラミングを楽しんでいます。
主に PHP を使っているのですが、インターネット検索で見つかる解説記事は、わかりやすさを優先するためか、計算量を犠牲にしたものも多く、なかなか実用的な例を見つけられずに苦労しました。
そこで、過去の自分が悩んだところ、知りたかったところを、まとめておきたいと思います。

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

Dijkstra 法とは

“Dijkstra” と書かれても、そもそも読み方が難しいです。
このアルゴリズムの考案者である、オランダのコンピュータ科学者エドガー・ダイクストラ（ Dijkstra ）さんの名前にちなんでいます。
日本語だと、ダイクストラ法（だいくすとらほう）、英語で調べるときは、 Dijkstra’s algorithm で調べられます。

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

たとえば、 Yahoo 路線情報のような、路線検索をイメージしてください。
出発駅から、到着駅までに、いくつか乗り換えがある場合、どの経路が最も最良か（時間的に、運賃的に最小か）が、一瞬で検索できます。
線路網は、一種のグラフとみなせるので、このような「膨大な選択肢の中から最適解を導き出す」というタスクにおいて、ダイクストラ法はまさに真価を発揮します。

今回は、 Dijkstra 法を 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 に記事を書いたことがある ので、興味のある方は読んでみてください）

スタート点からの距離を、優先度付きキューで管理して、新しい頂点につながるごとに、キューに追加していきます。
このデータ構造の優れた点は、「ヒープ(Heap)」という構造により、常にその時点で最も優先度の高い（つまり、スタート点から近い）到達点を、取り出し続けることができることです。

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

その時点で候補となる到達点について、最も近い点が選ばれ続けるため、常に最短の経路を確定し続けることが可能となります。
ここが、このアルゴリズムの肝です。

データ構造は優先度付きキューでなければいけないか？

ここで、疑問に思うひとがいるかもしれないので、少しだけ補足します。
（この章は、やや難しいので、読み飛ばしていただいても結構です。）

その時点で、最も近い点を選ぶのであれば、配列を用意して、 sort 関数や、 min 関数などで、最小のものを探索するのでも良いのではないか？
わざわざ、 SplPriorityQueue という、難しいデータ構造を選ばなくても良いのではないか？
という疑問があるかもしれません。

実際、インターネットで検索すると、 min で実装された事例も多く見られます。

しかし、配列の要素数を N とするとき、 sort 関数の計算量は O(NlogN), min 関数を使う場合は、 O(N) となります。
Heap 構造を使う SplPriorityQueue は、 O(logN) ですから、 N が大きくなるほど、この差は開いていきます。

SplPriorityQueue を利用した方が良いです。

生成 AI への実装依頼時の注意点

計算量の問題は、生成 AI に実装を頼むときにも注意が必要です。

生成 AI に、単純に「ダイクストラ法を PHP で作成してください」と頼むと、データ構造が単純な配列になっている（優先度付きキューではない）提案が返ってくることがあります。

しかし、前述の通り、配列の最小値(min など)で探索する場合、配列を全部探索するわけですから、計算量がかさんでしまいます。
選定対象となる辺の数が、100や1000くらいなら、計算時間がほぼ一瞬で終わるので、問題ないのですが、1万を超えると、実用的な時間では計算が終わりません。

PHP の優先度付きキュー(SplPriorityQueue)は、標準ライブラリなので、ライブラリを別途インストールすることなく利用できます。
実務上の具体的なデメリットが無いなら（たとえば、辺の数がものすごく少なく、 Spl ライブラリをインスタンス化する時間の方が重荷になるというような特殊な場合でなければ）、できるだけ 「実装の際には、計算量を意識し、 SplPriorityQueue を使ってください」と追加で指示することをおすすめします。

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

一般的に言われていることですが、ダイクストラ法の辺の重みは、非負（0以上）でなければいけません。

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

自分で実装してみると、なぜ非負という条件があるのか、わかってくるのではないかと思います。

計算量と実用度

計算量について、もう少し詳しく書いておきます。

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

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

日本全体でも、9000箇所程度しか駅は無いそうですから、バス停や、その他ランドマークを足したとしても、十分高速に動きます。

とても実用的なアルゴリズムと言えそうです。

逸話

ダイクストラさんが、ダイクストラ法を思いついたときの逸話があったので、引用します。

What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning [in 1956] I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.
—Edsger Dijkstra, 2001 https://www.informit.com/articles/article.aspx?p=3204806&seqNum=3

DeepL で日本語訳してもらいました：

「ロッテルダムからフローニンゲンへ、あるいは一般に、ある都市から別の都市へ移動する際の最短ルートとは何か。これは最短経路を求めるアルゴリズムであり、私が約20分で考案したものです。ある朝［1956年のこと］、私は若い婚約者と一緒にアムステルダムで買い物をしていた。疲れてしまったので、カフェのテラス席に座ってコーヒーを飲みながら、これができるかどうか考えていたところ、最短経路のアルゴリズムを考案したのだ。先ほども言ったように、20分で思いついたものだ。実際、それは3年後の1959年に発表された。その論文は今でも読みやすく、実に素晴らしい出来栄えです。これほど素晴らしい理由の一つは、私が鉛筆も紙も使わずにそれを考案したことです。後で知ったことですが、鉛筆や紙を使わずに考案する利点の一つは、避けられる複雑さをほぼ必然的に排除せざるを得なくなる点にあります。結局、そのアルゴリズムは、私にとって大きな驚きでしたが、私の名声を築く礎の一つとなったのです。」

本人談ではありますが、たった20分で、しかも紙も鉛筆も使わずに頭だけで考え付いたというのは、本当にすごいことだと思います。