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

ダイクストラのアルゴリズムが重み付きグラフの最短経路を見つける様子を見てみましょう。

計算例 — ダイクストラ法による最短経路

ノード 0	0
ノード 1	3
ノード 2	8
ノード 3	2
ノード 4	8
最短経路	0 → 3 → 4 (cost: 8)

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

緩和こそがアルゴリズムの全体で、優先度付きキューは速さにすぎない 🖖

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

最も近い頂点が常に確定できる理由 🖖

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

コーヒー片手に二十分で考案 🖖

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

全プロセスの詳細解説

ノード 1（始点から一エッジ、コスト 4） 5 ステップ
ノード1は始点からコスト4の辺1本で結ばれているが、アルゴリズムはその距離を3と報告している。確定順序を順に追い、この3がどこから生じたのかを突き止めよ。
1. ダイクストラ法はノードを距離の近い順に確定させていき、一度確定したノードを再訪問することはない。この順序づけこそがアルゴリズムの全容であり、証明のすべてである。あるノードが確定した時点で、それ以上に低コストな経路が存在することはあり得ない。なぜなら、仮にそのような経路が存在するならば、すでにそのノードよりも遠くにある未確定ノードを経由しなければならないからである。
  
  $E = {(0, 1, 4), (0, 3, 2), (1, 2, 5), (1, 3, 1), (2, 4, 3), (3, 4, 6)}$
2. 始点から出る2本の直接の辺により、仮の距離として4と2が得られる。どちらもまだ確定した値ではなく、これらは上界に過ぎない。
  
  $settle 0 : d_{1} = 4, d_{3} = 2$
3. 最も近いのはノード3（距離2）であり、これが最初に確定する。その辺を緩和すると、ノード1へ至るコスト 2 + 1 = 3 の経路が見つかり、直接の辺によるコスト4よりも低くなる。これこそが問題の問いに答えるステップである。すなわち、隣接ノードへの最も安い経路は、必ずしもそのノードへの直接の辺であるとは限らない。
  
  $settle 3 (d = 2) : d_{1} = min (4, 2 + 1) = 3, d_{4} = 2 + 6 = 8$
4. ノード1が3で確定し、そこから辺を緩和することでノード2に距離8で到達する。
  
  $settle 1 (d = 3) : d_{2} = 3 + 5 = 8$
5. ノード4へは、距離8でノード3を経由して到達可能であり、ノード2を経由するもう一つの経路のコストは 8 + 3 = 11 となるため、より短い方が採用される。
  
  $settle 2, 4 : d_{4} = min (8, 8 + 3) = 8 ⟹ 0 \to 3 \to 4$
解答

ツールは各距離として 3、8、2、8、そして最短経路として 0 → 3 → 4 を表示する。教訓はノード1にある。直接の辺は最短経路ではなく、貪欲法による確定こそが、それを指数関数的ではなく低コストで発見することを可能にしている。ただし、この保証には1つの前提条件がある。重みが非負であることだ。負の辺が存在すると、早期に確定したノードが後から改善される可能性が生じ、ステップ1における証明は崩壊する。『負の辺』プリセットをクリックすると、2つの側面で同時に破綻する様子が観察できる。ノード3はどの経路からも生じ得ない−1という距離を返し、経路復元は「経路なし — 先行ノードがループを形成している」と出力して完全に断念する。すべての重みが非負であれば証明可能に正しいアルゴリズムから、誤った数値が出力され、経路も得られなくなるのである。

$d_{1} = 3 via node 3, not 4 direct; 0 \to 3 \to 4 = 8$

参考文献 (2)

The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.

42Math チーム · 更新 2026-06-11

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

5ノードの都市 - 5ノードの都市: 最短経路0→4
3×3グリッド - 3×3グリッド: 複数の最短経路が存在する
深さ優先 vs 幅優先 - 深い経路対広い経路: 貪欲法は失敗する
負の辺 - 負の辺: ダイクストラ法は失敗することがある