Dijkstra 法

Dijkstra 法は、辺の重みが非負のグラフで、一つの始点から他の全頂点への最短距離を求める。暫定距離を保持し、優先度付きキューから距離が最小の未確定頂点を取り出して確定し、その出辺を緩和する。

辺の長さを、画びょうをつなぐ糸の長さと考える。始点を持ち上げると近い画びょうから浮き上がる。アルゴリズムは距離計算でこの順序を作る。必要な条件は全ての辺の重みが非負であること。後続経路はコストを増やすだけで、確定した最小距離を下げられない。負辺があれば Bellman-Ford 法を検討する。本レッスンの負辺プリセットは、保証が破れる位置を示す。

Dijkstra 法の仕組み

dist、visited、優先度付きキューを持つ。始点の距離は 0、他は ∞。visited は距離が確定した頂点を記録し、キューは (distance, node) を最小値から取り出す。

取り出して確定する。 未訪問の u を取り出したら訪問済みにする。この時点で dist[u] は真の最短距離だ。他の未確定頂点へ向かう経路は、それ以上の距離にある探索境界を通る必要があり、非負辺ではそこからコストを減らせない。

緩和する。 重み w の辺 u → v で dist[u] + w < dist[v] を調べる。成立すれば dist[v] を下げ、前駆頂点を u とし、新しい (dist[v], v) を入れる。改善しなければ何も変えない。

通常の二分ヒープを使う遅延更新では、旧項目を探して書き換えず、小さい値の新項目を追加する。旧項目は古くなり、後で取り出したとき頂点が visited にあれば捨てる。decrease-key のための位置管理を省く代わりに、この項目を保持する。

Dijkstra 法のステップ

既定の重み付き有向グラフは A–F の六頂点で、A から始める。辺は A→B (2)、A→C (5)、B→C (1)、B→D (7)、C→D (2)、D→E (1)、D→F (3)、E→F (2)。

1. dist[A]=0、他を ∞ にする。キューは [(0,A)]。
2. A を確定する。緩和で B は 2、C は 5。キューは [(2,B), (5,C)]。
3. 距離 2 の B を確定する。B→C の 2+1=3 により C を 5 から 3 へ下げる。二辺の A→B→C が一辺の A→C より安く、辺数だけを数える BFS では判断できない。B→D で D は 9。キューは [(3,C), (5,C), (9,D)] となり、C の新旧項目が並ぶ。
4. 距離 3 の C を確定する。C→D の 3+2=5 で D を 9 から 5 に下げる。キューは [(5,C), (5,D), (9,D)]。
5. (5,C) を取り出す。C は確定済みなので捨てる。キューは [(5,D), (9,D)]。
6. 距離 5 の D を確定する。E は 6、F は 8 になる。キューは [(6,E), (8,F), (9,D)]。
7. 距離 6 の E を確定する。E→F の 6+2=8 は旧値と同じなので更新しない。キューは [(8,F), (9,D)]。
8. 距離 8 の F を確定する。出辺はなく、キューは [(9,D)]。
9. 古い (9,D) を捨て、キューが空になって終了する。

最終距離は A:0, B:2, C:3, D:5, E:6, F:8。確定順 A、B、C、D、E、F の距離 0、2、3、5、6、8 は単調非減少になる。C を 3 で取り出したとき、他の項目は全て 3 以上であり、非負辺では後続経路をそれより下げられない。

時間計算量と空間計算量

本レッスンの単純グラフでは時間 O((V + E) log V)、空間 O(V + E)。各辺は高々一度の緩和成功を起こし、遅延更新ヒープへの総挿入は O(E) 個。dist と visited は O(V)、ヒープは O(E) を使う。厳密にはヒープ操作は項目数に依存して O(log E) だが、単純グラフでは O(log V) と書ける。

decrease-key を使う Fibonacci ヒープなら理論上 O(E + V log V) にできる。ただし管理や定数のコストで利点が失われる場合もある。

境界ケース

• 到達不能な頂点はキューに入らず、確定せず、距離 ∞ のまま。
• 一頂点なら 0 で入れ、取り出して確定すると終了する。
• 同じ距離のどちらを先に確定しても、最終距離は変わらない。本レッスンは頂点の識別子で同点を処理し、軌跡を固定する。
• 重みゼロは合法で、複数頂点が同じ距離で続けて確定してよい。
• 一つの目標だけが必要なら、その頂点を確定した時点で停止できる。

よくある間違い

1. 負辺に適用する。 負辺プリセットでは B を 2 で確定した後、重み −5 の C→B が A→C→B のコスト −2 を示す。B は確定済みなので改善を拒否し、−2 ではなく 2 を報告する。B の赤い輪が誤りを示す。キューの工夫では失われた前提を戻せない。
2. 確定済み距離を直そうとする。 正しい非負重みモデルでは厳密な改善は起きない。起きたら辺の重みと実装を確認し、同じ確定の証明を使い続けない。
3. 異なる重みを BFS で比べる。 BFS が最小化するのは辺数であり、全ての辺のコストが同じなどの条件が必要になる。
4. 古い項目の検査を忘れる。 if u in visited: continue が旧項目による再処理を防ぎ、本レッスンの遅延削除を支える。
5. 挿入時に確定する。 挿入は経路の発見にすぎず、最小候補として取り出すときに確定する。

表示上の簡略化

優先度付きキューは読みやすい整列済みの行として描く。実際の二分ヒープは先頭の最小値とヒープ順だけを保証し、全体は整列されていない。表示コードは確定済みの隣接頂点を緩和しない（v not in visited）。この条件を省き、取り出し時の古い項目の検査に任せる実装も、非負重みでは同じ距離を得る。負辺への対応を変える場合は別の証明が必要で、元の Dijkstra 法の保証を引き継ぐことはできない。