最短経路アルゴリズムの完全解説：基礎から実務応用まで—Dijkstra・Bellman–Ford・A*・Floyd–Warshall・Johnsonほか主要手法と計算量の比較
エバープレイ編集部はじめに
最短経路アルゴリズムは、グラフ上で「ある点から別の点までの最もコストの小さい経路」を求めるための基礎的かつ重要な技術です。ネットワーク経路探索、地図の経路案内、物流計画、通信ルーティング、ロボットの経路計画など、IT分野の幅広い応用で用いられます。本稿では、問題の定義と種類、主要アルゴリズムの動作原理と計算量、実装上の注意点、高度な手法や実運用での工夫について、できるだけ正確にかつ具体的に解説します。
最短経路問題とは — 何を解くのか
最短経路問題は一般に、重み付き（あるいは重み無し）グラフ G=(V,E) と始点 s（と場合によっては終点 t）を与え、各辺に割り当てられたコストの合計が最小となる経路を求める問題です。代表的な分類は次の通りです。
- 単一始点最短経路（SSSP: Single-Source Shortest Paths）: ある始点 s からすべての頂点への最短経路を求める。
- 単一対最短経路（Single-Pair）: s から t までの最短経路のみを求める。
- 全点対最短経路（APSP: All-Pairs Shortest Paths）: すべての頂点対 (u,v) の最短経路を求める。
- グラフの形: 有向／無向、辺の重みが非負／負を許す、重みが時間依存など。
代表的なアルゴリズムと特徴
BFS（幅優先探索） — 重み無しグラフ
すべての辺の重みが等しい（あるいは無視できる）場合、幅優先探索で最短（辺数が最小）経路が得られます。計算量は O(V+E) で非常に効率的です。
Dijkstra法 — 非負重みの最短経路（SSSP）
非負の辺重みを持つグラフに対して、始点から各頂点への最短距離を求める代表アルゴリズムです。優先度付きキュー（ヒープ）を用いて「確定した最短距離を持つ頂点」を順に扱います。実装による複雑度の代表値は以下の通りです。
- 単純な二分ヒープ（binary heap）を用いると O((V+E) log V)、一般に O(E log V)
- フィボナッチヒープを用いると理論上 O(V log V + E)（実装は複雑）
正当性は、非負重みであれば最小距離の頂点を確定させる操作が局所的に安全であること（貪欲性）に基づきます。
Bellman–Ford（ベルマン–フォード） — 負重みを許すSSSP
負の辺重みがある場合に使えるアルゴリズムです。始点からの最短距離を求め、さらに負の閉路（負の重みのサイクル）が存在するかの検出も可能です。計算量は O(VE) で、大規模グラフでは重くなりますが、負の辺が存在するケースでは重要です。
SPFA（Shortest Path Faster Algorithm） — 実務上の工夫版
Bellman–Ford をキューによる緩和（relaxation）の順序最適化で高速化した手法です。多くの実データでは高速に動作することが多い一方、最悪計算量は O(VE)（場合によっては非常に遅い）で、特に特定の入力で発散的に遅くなることが報告されています。使う際は注意が必要です。
Floyd–Warshall — 全点対最短経路（APSP）
動的計画法に基づく APSP の古典アルゴリズムで、全頂点対の最短距離行列を直接求めます。計算量は O(V^3)、実装は簡潔で負の辺重みも扱えます（負の閉路がある場合は対応が必要）。頂点数が数百〜千を超えると計算コストが厳しくなります。
Johnson のアルゴリズム — スパースグラフ向け APSP
APSP をスパースなグラフで効率よく行う手法です。まず追加頂点と Bellman–Ford で「ポテンシャル」を計算して重みを再重み付け（非負化）し、各頂点からの Dijkstra を実行します。計算量は O(VE + V * (E log V))（簡略化して O(VE log V) と表現されることもあります）。E が V に近いスパースグラフで有効です。
A*（A スター） — ヒューリスティック探索（単一対向け）
A* は目的地が明確な単一対問題で強力な手法です。各頂点に評価関数 f(n)=g(n)+h(n)（g が始点からの既知コスト、h が目的地までの推定コスト）を用い、h が「過小評価（admissible）」なら最適解が保証されます。h が一貫（consistent）であれば探索効率がさらに良く、オープンセットの再展開を避けられます。適切なヒューリスティック（例：地理データならユークリッド距離、マンハッタン距離）が鍵です。最悪時の計算量は指数的になる可能性がありますが、実用上は大幅に探索空間を削減できます。
双方向探索（Bidirectional Search / Bidirectional Dijkstra）
開始点からの探索と目的点からの逆探索を同時に行い、両者が出会ったところで解を構築する手法です。探索領域を大きく削減できることが多く、特に単一対問題で有効です。実装では重み付きグラフに対する逆辺の管理や停止条件の扱いに注意が必要です。
DAG（有向非巡回グラフ）に特化した手法
グラフが有向非巡回（DAG）であれば、トポロジカルソートに基づく一次走査で SSSP が O(V+E) で解けます。負の辺があっても問題ありません（閉路がないため）。
K 最短経路問題
単一対に対して最短経路以外に上位 K の経路を求める場合、Yen のアルゴリズム（単純経路の上位 K）や Eppstein のアルゴリズム（重複経路を含むが高速）などがあります。用途は多様で、冗長経路の確保や複数候補の比較に使われます。
計算量とデータ構造の選び方
実装面では、隣接リストと隣接行列の選択が性能に直結します。エッジが疎（E≈V）であれば隣接リスト＋ヒープが有利、密なグラフでは隣接行列や Floyd–Warshall が競合します。また、優先度付きキューの実装（二分ヒープ、カスタムヒープ、フィボナッチヒープなど）で理論的な差が出ますが、実務では単純な二分ヒープや pairing heap が扱いやすく高速です。
実運用での技術・工夫
現実世界の大規模経路探索（例：道路ネットワーク、ナビゲーション）では、単純な Dijkstra や A* だけでは遅いため、事前処理（プリプロセス）や補助データ構造を用いて高速化します。代表的な手法は次の通りです。
- Contraction Hierarchies（縮約階層）: 頂点の縮約とショートカット追加により高速なクエリを可能にする。道路網で極めて有効。
- ALT（A* + Landmarks + Triangle inequality）: ランドマークからの距離を使ったヒューリスティックで A* を強化。
- Hub Labeling: 各頂点にハブラベルを作り、クエリ時に高速に距離を得る。応答は非常に速いが前処理とメモリが重い。
- 並列化・分散処理: 大規模グラフやストリーミングの更新に対して並列処理や分散アルゴリズムを用いる。
実装上の注意点と落とし穴
- 負の辺: Dijkstra は非負重みが前提。負の辺がある場合は Bellman–Ford などを使う必要がある。
- 負の閉路: Bellman–Ford は検出可能。負の閉路が存在すると「最短」が定義できない（任意に小さくできる）。
- 浮動小数点: 実数重みを扱う場合、比較の精度や累積誤差に注意。イコール判定は避ける。
- メモリ: APSP（行列）やハブラベリングはメモリを大量に消費する。
- 経路復元: predecessor 配列を維持して遡ることで経路そのものを得る。複数最短経路や同コストの扱いを明確にしておく。
- 動的グラフ: エッジの追加・削除が頻繁な場合は incremental / dynamic SSSP の手法や再計算コストの見積りが必要。
応用例（実世界のユースケース）
- 地図サービス（Google Maps 等）: 道路ネットワークの最短経路や到達時間推定に複合的な手法（A*, Contraction Hierarchies 等）を利用。
- 通信ネットワーク: ルーティングプロトコル（OSPF など）は Dijkstra ベースでネットワークの到達性を決定。
- 物流・配送最適化: 制約付き経路問題や複数目的最適化と組合せて利用。
- ロボット: A* やその派生（動的ヒューリスティック、時間依存コスト）で経路計画を行う。
まとめ
最短経路アルゴリズムは単純な問題に見えますが、重みの符号、グラフのサイズや密度、応答時間の要件、メモリ制約、動的な変化、実際の地理情報に基づくヒューリスティックなど、実用上考慮すべき要素が多数あります。基礎として Dijkstra、Bellman–Ford、Floyd–Warshall を押さえ、用途に応じて A*、Johnson、双方向探索、スパース向け高速化手法やプリプロセス技術（Contraction Hierarchies、ALT、Hub Labeling 等）を選ぶのが一般的です。実装ではデータ構造と数値処理の正確さに注意し、ベンチマークを基に選択してください。
参考文献
- Shortest path problem — Wikipedia
- Dijkstra's algorithm — Wikipedia
- Bellman–Ford algorithm — Wikipedia
- Floyd–Warshall algorithm — Wikipedia
- A* search algorithm — Wikipedia
- Johnson's algorithm — Wikipedia
- Contraction Hierarchies — Wikipedia
- Yen's algorithm — Wikipedia (K shortest simple paths)
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
投稿者プロフィール
