ダイクストラ法による最短経路

ダイクストラ法は、非負のエッジ重みを持つグラフの最短経路を探索します。貪欲法を用いて訪問済みノードを維持し、緩和処理 d(v) = min(d(v), d(u) + w(u,v)) によって最短距離を更新します。フィボナッチヒープ優先度キューを用いることで、計算量は O(E + V log V) に最適化されます。

ダイクストラ法は始点から探索範囲を外へ広げ、常に未確定の頂点のうち最も近いものを確定します。すべての辺の重みが非負なので、後からどんな迂回路を通っても、すでに見つけた短い経路を上回ることはありません。いったん頂点が確定すれば、その距離は最終的なもので二度と見直されません。だからこそ経路案内やOSPFのようなルーティングプロトコルは、信頼できる最短経路の計算にこれを利用します。

エドガー・ダイクストラは1956年、アムステルダムのカフェのテラスで休憩しながら、鉛筆も紙も使わず約二十分でこのアルゴリズムを考案しました。彼は計算機ARMACのデモ用の問題を探しており、オランダの二都市ロッテルダムとフローニンゲンの間の最短経路を選びました。三年後、わずか三ページほどの論文で発表され、計算機科学で最も引用される成果の一つとなりました。