ベルマン–フォード法とは？負の重みと負の閉路検出を徹底解説する単一始点最短経路アルゴリズムの完全ガイド

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

ベルマンフォード法とは — 概要と適用範囲

ベルマンフォード法（Bellman–Ford アルゴリズム）は、単一始点最短経路問題を解く古典的なアルゴリズムの一つです。重み付き有向グラフ（または無向グラフを有向辺として扱う）に対して、指定した始点から各頂点への最短距離を求められます。特に他の代表的なアルゴリズム（例：ダイクストラ法）と比べて重要な特徴は、「負の重みを持つ辺」を扱える点と、「負の閉路（負サイクル）の検出」が可能な点です。

アルゴリズム名は Richard Bellman と Lester R. Ford, Jr. にちなんでおり、Edward F. Moore による独立した寄与も知られています。

基本的な考え方（緩和の反復）

ベルマンフォード法は「緩和（relaxation）」と呼ばれる操作をグラフ中のすべての辺に対して繰り返します。緩和とは、ある辺 (u → v, 重み w) に対して現在知られている dist[u] と dist[v] を比較し、経由することで v の距離が短くなるならば更新する操作です。

  • 初期化：始点 s に対して dist[s] = 0、その他の頂点の距離は +∞ に設定。
  • 反復回数：頂点数を V とすると、最短経路は最大でも V−1 エッジまでしか使わないため、すべての辺に対する緩和を V−1 回繰り返す。
  • 負の閉路検出：さらにもう1回すべての辺をチェックして緩和可能ならば、始点から到達可能な負の閉路が存在することを示す。

擬似コード（概念）

以下は典型的なアルゴリズムの擬似コードです（動作理解用）。

initialize:
  for each vertex v:
    dist[v] = +∞
    pred[v] = null
  dist[s] = 0

for i = 1 to V-1:
  for each edge (u, v, w):
    if dist[u] != +∞ and dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
      pred[v] = u

// 負の閉路の検出
for each edge (u, v, w):
  if dist[u] != +∞ and dist[u] + w < dist[v]:
    report "負の閉路あり"

正当性（なぜ V−1 回で良いのか）

最短経路に含まれる辺数はサイクルを含まない限り最大で V−1 です。各反復で、ソースから長さ k の経路で到達できる頂点の距離が確定的に伝播するため、V−1 回の緩和で最短距離は得られます。もしさらに緩和できるならば、それは負の重みのサイクルを示しています（サイクルを回るたびに距離が縮むため）。

計算量とメモリ

  • 時間計算量：O(VE)（V は頂点数、E は辺数）。辺の数に比例する内部ループを V−1 回行うため。
  • 空間計算量：O(V + E)（辺を列挙して保持する場合。実装上は距離配列と前任者配列で O(V) を使用）。
  • 特徴：ダイクストラ法（ヒープ実装で O(E log V)）より遅いが、負の重みを扱える点で優位。

例：小さなグラフでの手順

例として頂点 {A, B, C}、辺 A→B(3), A→C(8), B→C(−5) を考えます。始点は A。

  • 初期：dist[A]=0, dist[B]=∞, dist[C]=∞
  • 1回目の緩和：A→B により dist[B]=3。A→C により dist[C]=8。B→C によれば dist[C]=3+(−5)=−2 に更新。
  • 2回目の緩和（V−1=2 回目）：A→B は変化なし。A→C は変化なし。B→C も変化なし。最短値が確定。
  • 負の閉路チェック：もしさらに更新が起きれば負の閉路を示すが、この例ではなし。

負の閉路とその扱い

ベルマンフォード法は負の閉路を検出できます。ただし検出されただけでは最短経路が定義されない（閉路を何回も回ればコストがどんどん下がるため）。実務では負の閉路がある場合の振る舞いを明確に決めておく必要があります（例：その頂点を「無限に小さい距離」として扱う、探索を中止してエラー報告する等）。

実装上の注意点・最適化

  • 早期停止：ある反復で一切の更新が起きなければ以降の反復は不要。多くの実装で有効な簡単な最適化。
  • データ型：重みが大きい整数や負の値が混在する場合、オーバーフローに注意（C/C++では long long 等を適切に使う）。
  • 表現方法：辺のリスト（edge list）でそのままループする実装が分かりやすく一般的。隣接リストから全辺を列挙して処理することも可能。
  • 経路復元：pred（前任者）配列を保持し、目的地から pred をたどれば最短経路を復元できる。ただし負の閉路が絡む場合は復元が無意味になる。

発展と関連アルゴリズム

  • ダイクストラ法との比較：負の辺がない場合はダイクストラが一般的に高速。負の辺がある場合はベルマンフォードが安全。
  • Johnson のアルゴリズム：全点対最短経路を求める際、グラフに負の辺が含まれている場合はまずベルマンフォードで再重み付けを行い（負の閉路がないことを確認）、その後各頂点からダイクストラを実行する手法。
  • SPFA（Shortest Path Faster Algorithm）：ベルマンフォードの実用的な変種で、キューを使って更新が必要な頂点のみを処理することで平均的に高速化できる場合がある。ただし最悪計算量は依然として O(VE) もしくはそれ以上になり得るため理論的保証はない。
  • 距離ベクトルルーティング：ネットワークルーティングプロトコル（例：RIP）はベルマンフォード型の考え方（距離ベクトルの交換と更新）を採用している。

よくある誤解と実務上の注意

  • 「ベルマンフォードは常に遅い」は文脈依存。疎グラフや小規模グラフ、負の辺がある場合には十分実用的。
  • SPFA による高速化は万能ではない。特定のグラフでは非常に遅くなるケース（悪化事例）が存在する。
  • 負の重みは現実問題での利用に注意。物理的距離が負になることは原則ないが、コスト差や補正値などアプリケーション固有の値としてはあり得る。

実装例（ポイントのみ）

実装の際は以下の点を押さえておくと良いです：

  • 辺は (u, v, w) の構造体／タプルで保持する（edge list）。
  • dist 配列は初期に大きな正の値（∞）を入れておき、更新時は dist[u] が ∞ でないことを条件にする。
  • 反復ごとに「更新があったか」をフラグで持ち、無ければループを早期終了する。
  • 負の閉路検出は最後の1回の全辺走査で行う。

用途と実世界での適用例

  • ネットワークルーティング（距離ベクトルプロトコルの概念的基盤）。
  • 金融や最適化問題のモデル化で、コスト調整や再重み付けが必要な場合。
  • アルゴリズム研究や競技プログラミングでは負の辺が含まれる最短経路問題の標準解法として頻出。

まとめ

ベルマンフォード法は、負の重みを扱い負の閉路を検出できるという点で重要かつ汎用性の高い最短経路アルゴリズムです。計算量は O(VE) とやや高めですが、正確性と単純さから教育・実務の両面で広く使われています。用途に応じてダイクストラ法や Johnson 法、SPFA などと使い分けることが肝要です。

参考文献

カテゴリー
IT
前の記事
単一始点最短経路問題（SSSP）完全ガイド：DijkstraからJohnsonまでのアルゴリズム比較と実践ポイントNew!!
2025年11月20日
次の記事
フロイド–ワーシャル法とは？全点対最短経路の基礎・実装・負の重みと負の閉路への対処New!!
2025年11月20日