Bellman-Ford 法

2025年10月20日

Bellman-Ford 法

英語表記: Bellman-Ford Algorithm

概要

Bellman-Ford 法は、「アルゴリズムと計算量」における「最短経路」問題を解決するための基本的な「グラフアルゴリズム」の一つです。このアルゴリズムの最大の特徴は、経路のコスト（重み）が負の値を持つ辺（エッジ）が存在するグラフであっても、正確に最短経路を見つけ出すことができる点です。ただし、途中の経路を永遠に短縮できてしまう「負の閉路」（ネガティブサイクル）が存在するかどうかも同時に検出できる、非常に頼りになる手法です。

詳細解説

Bellman-Ford 法は、最短経路を見つけるという点で有名なDijkstra（ダイクストラ）法と同じ目的を持ちますが、その適用範囲と計算効率において明確な違いがあります。このアルゴリズムが「グラフアルゴリズム」の分野で重要視されるのは、Dijkstra法が苦手とする負の重み付きグラフを扱えるからです。

目的と背景

最短経路問題は、ある始点から他のすべての頂点への最もコストの低い道筋を見つけることが目的です。通常のグラフでは、重みは時間や距離といった正の値を取りますが、金融取引における利益、または特定の行動による時間の短縮など、「コストがマイナスになる」状況をモデル化する必要がある場合に負の重みが発生します。Bellman-Ford 法は、まさにこの複雑な状況に対応するために開発されました。

動作原理：緩和操作とV-1回反復

Bellman-Ford 法の動作の核となるのは、「緩和操作（Relaxation）」と「反復回数制限」です。

初期化: まず、始点以外のすべての頂点への暫定的な最短距離を無限大に設定し、始点への距離を0とします。
緩和操作の反復: グラフ内のすべての辺（エッジ）に対して、以下の緩和操作を繰り返し適用します。
- 緩和操作とは、「現在の頂点までの最短距離」と「その頂点から次の頂点へ移動するコスト」を合計した値が、「次の頂点までの現在の最短距離」よりも短い場合に、最短距離を更新する操作です。
反復回数の制限: グラフに頂点（ノード）が$V$個ある場合、最短経路が確定するために必要な緩和操作の最大回数は、$V-1$回です。なぜなら、最短経路は単純経路（同じ頂点を二度通らない経路）であり、最大で$V-1$本の辺しか含まないからです。Bellman-Ford 法は、この$V-1$回の反復を厳密に実行します。

負の閉路の検出

$V-1$回の反復が終了した後、Bellman-Ford 法は非常に重要な最終チェックを行います。

もし、$V$回目の緩和操作を行った際に、さらに距離を短縮できる頂点が存在した場合、それはグラフの中に「負の閉路」（コストの合計が負になるループ）が存在することを意味します。負の閉路があると、その閉路を永遠に周回することで、理論上は距離を無限に短くできてしまうため、最短経路は定義できなくなります。Bellman-Ford 法は、最短経路を求めるだけでなく、この「解が存在しない」状況を検出できるという点で、非常に優れたアルゴリズムです。

計算量（アルゴリズムと計算量の観点）

このアルゴリズムは、すべての辺（E）に対して$V-1$回の緩和操作を行うため、計算量は$O(V \cdot E)$となります。これは、辺の数$E$が頂点の数の2乗に近い密なグラフにおいては、Dijkstra法の$O(E \log V)$や$O(V^2)$と比較して遅くなる傾向があります。しかし、「アルゴリズムと計算量」の分野において、負の重みを許容しつつ多項式時間で解を導出できるという点で、Bellman-Ford 法の存在意義は非常に大きいと言えます。

具体例・活用シーン

Bellman-Ford 法の理解を深めるためには、「負の重み」が何を意味するのかを具体的にイメージすることが大切です。

1. 負の重みのアナロジー：節約ルートを探す旅

最短経路問題は通常、時間や燃料を最小化する旅に例えられますが、Bellman-Ford 法が必要なのは、旅の途中で「利益」が発生するケースです。

ストーリー： あなたは、ある都市Aから都市Zへ向かう貧乏旅行者だとしましょう。

通常の辺（正の重み）: 交通費や宿泊費など、お金（コスト）がかかる移動です。
負の重みを持つ辺（コストのマイナス）: これは、移動する代わりにお金が手に入るイベントです。例えば、「この街でボランティア活動に参加すると、移動費を差し引いても少額の報酬がもらえる」「特定の場所で無料のシャトルバスに乗り、さらにクーポン券をもらう」といった状況です。

あなたの目的は、都市Zに到着するまでに、最終的に手元に残るお金（または使ったお金）を最大化（最小化）するルートを見つけることです。Bellman-Ford 法は、このような「コストを節約できるチャンス（負の重み）」を適切に組み込みながら、全体として最もお得なルートを計算してくれます。

2. 負の閉路のアナロジー：無限の貯金ループ

もし、ある3つの街B、C、Dを回るルート（B→C→D→B）があり、それぞれの移動で必ず少しずつお金が増えてしまう（合計コストが負になる）場合、あなたは永遠にこの3つの街を回り続けるだけで無限に儲けることができます。これが「負の閉路」です。Bellman-Ford 法は、このような非現実的な無限ループの存在を教えてくれるのです。

3. 実際の活用シーン（IT分野）

ルーティングプロトコル: 過去には、ネットワークのルーティングプロトコルの一つであるRIP（Routing Information Protocol）の初期バージョンで、Bellman-Ford 法の原理が使用されていました。これは、ネットワーク内のホップ数（通過するルーターの数）をコストとして、最短経路を決定するために使われていました。
金融取引（裁定取引の検出）: 異なる市場間で為替レートや商品価格にわずかな差がある場合、その差を利用してリスクなく利益を得る取引（裁定取引、アービトラージ）が可能です。この取引をグラフの負の閉路としてモデル化することで、裁定機会を検出するためにBellman-Ford 法が応用されることがあります。