Dijkstraアルゴリズムのステップバイステップ解説

Dijkstraアルゴリズム

Dijkstraアルゴリズムは、非負の辺の重みを持つ重み付きグラフにおいて、単一ソースノードから他のすべてのノードへの最短経路を見つけます。コンピュータサイエンスとネットワーキングにおける最も重要なアルゴリズムの一つです。

Dijkstraの動作原理

1. 初期化 — ソースノードの距離を0、他のすべてを無限大に設定。すべてのノードを未訪問セットに追加。
2. 選択 — 最小の暫定距離を持つ未訪問ノードを選択。これが現在のノード。
3. 隣接ノードの緩和 — 現在のノード経由の距離を計算。以前の記録より短い場合、更新。
4. 訪問済みにマーク — 現在のノードを未訪問セットから削除。
5. 繰り返し — すべての到達可能なノードが訪問されるまで続行。

初期:  A=0, B=∞, C=∞, D=∞
A訪問: B=4, C=2, D=∞     (A→B=4, A→C=2経由)
C訪問: B=3, D=7           (C→B=1, C→D=5経由)
B訪問: D=6                (B→D=3経由)
D訪問: 完了

優先度キューによる最適化

ナイーブな実装ではすべてのノードをスキャンしてO(V²)になります。**最小ヒープ（優先度キュー）**を使用するとO((V + E) log V)に削減され、疎なグラフではより高速です。

なぜ非負の重みが必要か

Dijkstraアルゴリズムは、ノードが訪問されたらその最短距離が確定すると仮定します。負の辺の重みはこの仮定を破り、不正確な結果を引き起こす可能性があります。

他のアルゴリズムとの比較

アルゴリズム	負の重み	時間計算量
Dijkstra	不可	O((V+E) log V)
Bellman-Ford	可	O(V·E)
Floyd-Warshall	可	O(V³)