グラフにおける最短経路問題
主要な最短経路アルゴリズムを調査：重みなしのBFS、非負の重みのDijkstra、負の重みのBellman-Ford、全ペアのFloyd-Warshall。計算量とユースケースを比較します。
Shortest Path
詳細な説明
最短経路問題
ノード間の最短経路を見つけることは、コンピュータサイエンスで最も研究されている問題の一つです。異なるグラフの特性には異なるアルゴリズムが必要です。
アルゴリズム選択ガイド
| シナリオ | アルゴリズム | 時間計算量 |
|---|---|---|
| 重みなしグラフ | BFS | O(V + E) |
| 非負の重み | Dijkstra | O((V+E) log V) |
| 負の重み | Bellman-Ford | O(V · E) |
| 全ペア | Floyd-Warshall | O(V³) |
| DAG（任意の重み） | DAG緩和 | O(V + E) |
重みなしグラフのBFS
すべての辺が等しい重み（または重み1）の場合、BFSは自然に最短経路を見つけます。
非負の重みのDijkstra
Dijkstraアルゴリズムは貪欲アプローチを使用：常に最も近い未訪問ノードを処理します。
負の重みのBellman-Ford
Bellman-FordはすべてのV-1回辺を緩和します。負のサイクルを検出できます。
A*探索
Aはヒューリスティック関数h(n)でDijkstraを拡張します。ヒューリスティックが許容的な場合、Aは最適でDijkstraより高速です。
ユースケース
GPSナビゲーションシステムはDijkstraまたはA*を使用して走行ルートを見つけます。OSPFやIS-ISなどのネットワークプロトコルはパケットルーティングに最短経路アルゴリズムを使用します。ゲームAIはマップ上のキャラクターパスファインディングにA*を使用します。