ダイクストラ法とは？
ダイクストラ（Dijkstra）法は、重み付きグラフで一つの開始ノードからすべての他のノードへの最短経路を求めるアルゴリズムです。1956年にエドガー・ダイクストラが考案し、カーナビの経路探索がまさにこのアルゴリズムの応用です。
なぜ重要か？
ダイクストラ法はコーディングテストと実務の両方で核心的なアルゴリズムです。
- •実務活用: カーナビ、ネットワークルーティング、ゲームAI経路探索
- •コーディングテスト頻出: Google、Amazon、日本の大手IT企業で出題頻度が高い
- •拡張性: ベルマンフォード、A*アルゴリズムなど高度なアルゴリズムの基盤
動作原理
ダイクストラ法は貪欲法（Greedy）戦略を使用します。各ステップで、現時点で発見された最短距離が最も短いノードを選択します。
ステップ1. 開始ノードの距離を0、残りを無限大で初期化します。
ステップ2. 未訪問ノードの中で距離が最も短いノードを選択します。
ステップ3. 選択したノードの隣接ノードの距離を更新します。
- •新距離 = 現在のノード距離 + 辺の重み
- •新距離 < 既存距離なら更新
ステップ4. すべてのノードを訪問するまでステップ2〜3を繰り返します。
時間計算量
| 実装方式 | 時間計算量 |
|---|---|
| 配列探索 | O(V²) |
| 優先度キュー（ヒープ） | O((V + E) log V) |
ノードが多い場合は必ず優先度キュー（最小ヒープ）を使用する必要があります。優先度キューを使えば「距離が最短のノード」をO(log V)で取り出せます。
核心的な制約条件
負の重みがある場合は使用できません。 ダイクストラ法は、一度確定した最短距離が変わらないという仮定（貪欲法）に基づいています。負の重みがあるとこの仮定が崩れます。
負の重みがあるグラフではベルマンフォードアルゴリズムを使用します。
他の最短経路アルゴリズムとの比較
| アルゴリズム | 負の重み | 時間計算量 | 用途 |
|---|---|---|---|
| ダイクストラ | 不可 | O((V+E) log V) | 単一始点 |
| ベルマンフォード | 可能 | O(V × E) | 単一始点 + 負の重み |
| フロイド-ワーシャル | 可能 | O(V³) | 全ペア最短経路 |
実践テクニック
- •優先度キューから取り出したノードの距離が確定済み距離より大きければスキップ（時間節約）
- •経路復元が必要なら、prev配列に前のノードを記録
- •2次元グリッドでも座標をノードに変換して適用可能
AlgoNoteで直接確認しましょう
ダイクストラ法がノードを一つずつ確定しながら最短距離を更新していく過程を、AlgoNoteで視覚的に確認できます。グラフの重みを変えて、経路がどう変わるか実験してみてください。