単一始点最短経路問題（SSSP）完全ガイド：DijkstraからJohnsonまでのアルゴリズム比較と実践ポイント

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

単一始点最短経路とは

単一始点最短経路（Single-Source Shortest Paths, SSSP）問題は、グラフ理論とアルゴリズムの基本的かつ重要な問題の一つです。与えられた重み付きグラフと一つの始点頂点 s に対して、始点 s からグラフ内のすべての頂点 v への「最短経路（距離または重みの和が最小）」を求める問題を指します。ここでの「最短」は、経路上の辺の重みの合計が最小であることを意味します。

問題の定式化

  • 入力：有向または無向のグラフ G=(V,E) と、各辺 e に割り当てられた重み w(e)。始点 s∈V。
  • 出力：各頂点 v∈V に対する距離 d(s,v) と（必要ならば）前置き情報 predecessor(v) により表現される最短パス。

特殊ケースとして、全ての辺の重みが等しい（あるいは重みなし）場合は幅優先探索（BFS）で解け、負の重みが存在すると Dijkstra 法は使えません。負の重みを含む場合は Bellman–Ford 法などが用いられ、負の閉路（負の長さのサイクル）が存在すると「最短経路」が定義できない（任意に小さくできる）ことに注意が必要です。

代表的アルゴリズム

Dijkstra（ダイクストラ）法

非負の辺重みを持つグラフに対して最も広く使われるアルゴリズムです。始点から距離が確定した頂点を順に選び、そこから到達可能な未確定頂点の距離を緩和（relaxation）していきます。実装上は優先度付きキュー（ヒープ）を使います。

  • 正確性：全ての辺重みが非負であることが前提。
  • 計算量（代表例）：二分ヒープを使うと O((V+E) log V)（通常は O(E log V）と表記）。フィボナッチヒープを使えば O(E + V log V) に改善。
  • 用途：ルーティング（最短経路探索）、地図アプリなど実用面で広く利用。

Bellman–Ford（ベルマン–フォード）法

辺に負の重みが許される一般的なアルゴリズムです。頂点数 V に対して最大 V-1 回のエッジ緩和を行い、これで安定しない場合は負の閉路が存在すると判定します。

  • 計算量：O(VE)。
  • 利点：負の重みを扱えることと、負の閉路の検出が可能。
  • 欠点：計算量が大きく、辺が多いグラフでは遅い。

SPFA（Shortest Path Faster Algorithm）

Bellman–Ford の改良的な実装で、緩和が必要になった頂点だけをキューに入れて処理することで平均的に高速化を図る手法です。しかし最悪計算量は O(VE) で、特定の悪い入力（例えば負の閉路に近い構造）では非常に遅くなることがあります。

DAG（有向非巡回グラフ）向けアルゴリズム

グラフが有向非巡回（DAG）であるならば、トポロジカルソートを行い、ソート順に一回の緩和で最短経路を求められます。計算量は O(V+E) です。

A*（エースター）探索

A* はヒューリスティックを用いた最短経路探索で、主に始点から特定の目標頂点までの最短経路（単一始点単一終点）を高速に求めるために使われます。ヒューリスティックが「過小評価（admissible）」であれば最短性が保証されます。A* は SSSP アルゴリズムというよりは点対点探索に特化した派生と考えるとよいでしょう。

Johnson のアルゴリズム

重みが負の辺を含むが負の閉路がないグラフで、全点対最短路（All-Pairs Shortest Paths）を効率的に求めるための手法です。まず仮想頂点を追加して Bellman–Ford を一度実行しポテンシャル関数で辺重みを非負に再重み付けし、その後各頂点から Dijkstra を実行します。

データ構造と最適化

  • 優先度付きキュー（ヒープ）：二分ヒープ、二項ヒープ、フィボナッチヒープ、ペアリングヒープなど。理論的にはフィボナッチヒープが良いが実装や定数因子で二分ヒープやペアリングヒープの方が実用的なことが多い。
  • Dial 法・ラジックスヒープ：辺重みが非負整数でかつ上限が小さい場合、Dial のアルゴリズム（配列ベースのバケット）やラジックスヒープにより O(E + V C) や O(E + V log C) などの高速化が可能（C は最大距離や最大辺重みに依存）。
  • メモリ：距離配列 d[v] と前駆配列 predecessor[v] を保持しておくことで、最短距離の他に経路そのものを復元可能。

負の重みと負の閉路の扱い

負の辺が存在するグラフでは、単に Dijkstra を適用してはいけません。Bellman–Ford は負の重みを扱い、負の閉路を検出できます。負の閉路が到達可能である場合、最短経路は定義されません（コストを無限に小さくできるため）。システム設計上は負の辺が意味を持つか慎重に考える必要があります（例：コスト補助やペナルティのモデリングなど）。

アルゴリズム選択のガイドライン

  • 辺重みがすべて非負であり、単一始点から全頂点へ最短距離を求めたい：Dijkstra（適切なヒープで実装）。
  • 負の辺がある（負の閉路がないことが期待される）：Bellman–Ford、最悪計算量は許容されるかを検討。
  • グラフがスパース（E ≪ V^2）で多数回クエリがくる（多くの始点から求める必要がある）：Johnson を検討。
  • 単一始点・単一終点で高速化したい：A*（良いヒューリスティックがある場合）。
  • 辺重みが小さい整数値：Dial 法やラジックスヒープで高速化可能。

実装上の注意点・落とし穴

  • 距離の初期値は無限大（あるいは十分大きな値）で初期化し、始点のみ 0 にする。
  • 負の辺を誤って許して Dijkstra を使うと誤った結果になる。
  • 浮動小数点の重みを扱う場合は比較や累積誤差に注意。等価判定はイプシロンを使うなどの工夫が必要。
  • 経路復元は predecessor 配列を辿るが、負の閉路が絡む場合は無限ループに注意。
  • スケーラビリティ：大規模グラフ（数百万ノード、数千万辺）ではメモリとI/Oがボトルネックになる。外部記憶アルゴリズムや分散処理（GraphX、Pregel 系）を検討する。

応用例

  • ナビゲーション・地図アプリ（道路ネットワークの経路探索）
  • ネットワークルーティング（OSPF、内部的には Dijkstra が利用されることがある）
  • 時刻表や交通網における最短（最短時間・最小コスト）経路
  • ゲーム AI の経路探索（A* がよく用いられる）
  • 分子経路解析や電力ネットワークの解析など、グラフベースの問題全般

計算量の比較（概観）

  • BFS（重みなし）: O(V+E)
  • Dijkstra（二分ヒープ）: O(E log V)
  • Dijkstra（フィボナッチヒープ）: O(E + V log V)
  • Bellman–Ford: O(VE)
  • SPFA: 平均は速いが最悪 O(VE)
  • Floyd–Warshall（全点対）: O(V^3)
  • Johnson（全点対, sparse に有利）: Bellman–Ford + V×Dijkstra

まとめ（設計上のポイント）

単一始点最短経路問題は理論的にも実用的にも重要で、グラフの性質（辺の重みの符号、グラフの密度、クエリの種類）に応じて最適なアルゴリズムが異なります。実装では数値表現、データ構造選択、負の重みの有無、スケーラビリティを意識してアルゴリズムを選定してください。現実のアプリケーションでは、理論的な最良のアルゴリズムよりも実装の単純さや定数因子、ライブラリの成熟度が重要になることが多い点も覚えておくと良いでしょう。

参考文献

カテゴリー
IT
前の記事
最短経路アルゴリズムの完全解説：基礎から実務応用まで—Dijkstra・Bellman–Ford・A*・Floyd–Warshall・Johnsonほか主要手法と計算量の比較New!!
2025年11月20日
次の記事
ベルマン–フォード法とは？負の重みと負の閉路検出を徹底解説する単一始点最短経路アルゴリズムの完全ガイドNew!!
2025年11月20日