ダイクストラ法
ダイクストラ法（Dijkstra's algorithm）は、重み付きグラフにおいて、ある単一の始点から他の全ての頂点への最短経路を求めるアルゴリズムである。1956年にオランダの計算機科学者エドガー・ダイクストラによって考案された。
このアルゴリズムは、経路を構成する各辺（エッジ）の重みが非負である場合にのみ正しく機能する。そのため、現実世界の道路網（カーナビゲーション）やコンピュータネットワークのルーティングプロトコル（OSPFなど）のように、距離が負数にならない状況で最短経路を探索するために広く利用される。
概要
ダイクストラ法は貪欲法の一種であり、各ステップで、それまでに計算された最短距離に基づき、未訪問のノードの中から最も距離が短いノードを選択する。そして、そのノードを経由した場合の新しい経路コストを計算し、既存のコストよりも小さければ更新するという処理を繰り返す。
アルゴリズムは、始点から各ノードまでの最短距離を記録する配列（またはリスト）を維持し、この値を段階的に改善していく。全てのノードを訪問し終えるとアルゴリズムは終了し、始点から全ノードへの最短経路が確定する。
アルゴリズムの流れ
- 初期化:
- 始点ノードの距離を0に設定し、それ以外の全てのノードの距離を無限大（∞）で初期化する。
- 全てのノードを「未訪問」状態にする。
- 「未訪問」ノードのみを管理する集合（または優先度付きキュー）を用意する。
- 繰り返し:
- 「未訪問」ノードの中から、現時点で計算されている距離が最も短いノードを現在ノードとして選択する。
- 現在ノードを「訪問済み」状態に変更する。
- 現在ノードに隣接する全ての「未訪問」ノードについて、現在ノードを経由した場合の経路コストを計算する。
- `（現在ノードまでの距離 + 隣接ノードまでの辺の重み）`
- 計算したコストが、その隣接ノードに記録されている既存のコストよりも小さい場合、コストを新しい値に更新する。
- 全てのノードが「訪問済み」になるか、「未訪問」ノードの集合が空になるまで、上記プロセスを繰り返す。
計算量
ダイクストラ法の計算量は、「未訪問」ノードの中から最短距離のノードを探索する方法によって異なる。
- 線形探索: 全てのノードを順に確認して最短距離のノードを探す方法。計算量はO(V²)となる（Vは頂点の数）。
- 優先度付きキュー（Priority Queue）: ヒープなどを用いた優先度付きキューを使用すると、最短距離のノードをより効率的に発見できる。この場合の計算量はO((E + V) log V)または、辺の数が多い密なグラフではO(E log V)となる（Eは辺の数）。現代的な実装の多くは優先度付きキューを用いる。
特徴と限界
- 長所: 概念が比較的単純であり、貪欲法的なアプローチで最適解を保証する。
- 限界: 辺の重みが負であるグラフでは、正しい最短経路を発見できない場合がある。負の重みを含むグラフでは、ベルマン-フォード法を使用する必要がある。
応用分野
- ナビゲーションシステム: GPSなどで、2地点間の最短運転ルートを計算するために使用される。
- ネットワークルーティング: OSPFやIS-ISのようなルーティングプロトコルで、データパケットが経由する最適な経路を決定する。
- 物流・サプライチェーン管理: 輸送コストや時間を最小化する配送ルートを最適化する。
- ゲーム開発: 人工知能キャラクターがマップ上で目的地まで最短で移動する経路を見つけるために活用される。