ベルマン–フォード法とは？仕組み・コード・計算量をわかりやすく解説

ベルマン–フォード法が解く問題

ダイクストラ法は高速ですが、辺の重みが非負であることが必要です。返金、為替での利益、ゼロを下回るエネルギーコストなど、自然に負の重みが生じる問題もあります。ベルマン–フォード法はこうしたグラフを正しく扱えるうえ、負閉路（回るほどコストが際限なく小さくなるループ）のせいで最短経路が存在しない場合も検出できます。

このアルゴリズムの名前は、1950年代にそれぞれ類似の手法を発表したリチャード・ベルマン（Richard Bellman）とレスター・フォード・ジュニア（Lester Ford Jr.）に由来します。

考え方を言葉で説明すると

1. 開始ノードの距離を 0、ほかのすべてのノードの距離を無限大にします。
2. V − 1 回繰り返します。重み w のすべての辺 u → v について、dist[u] + w < dist[v] なら dist[v] を更新します。
3. すべての辺をもう1回調べます。まだ距離が改善される辺があれば、負閉路があると報告します。

なぜ V − 1 回なのでしょうか。閉路を含まない最短経路が使う辺は高々 V − 1 本だからです。k 回目の後には、最短経路の辺数が k 本以下のノードはすでに正しい距離を持つので、V − 1 回で単純な経路がすべて網羅されます。

具体例で一歩ずつ確認

4つのノードと、辺 S→A（4）、S→B（5）、B→A（−3）、A→C（3）を持つ有向グラフです。辺はどの回でもこの順に処理します。

1回目で、A はまず S→A によって 4 になり、続いて B→A によって 2 に改善され、C は改善後の値を使います。ダイクストラ法なら B を調べる前に A を 4 で確定してしまいますが、これはまさに負の辺が引き起こす間違いです。

Pythonでの実装

ベルマン–フォード法は辺の単純なリストに対して動作するので、短く書けます。

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

重み −6 の辺 C → B を追加すると、B → A → C → B という閉路ができ、合計の重みは −3 + 3 − 6 = −6 になります。そのため、追加の1回で検出されます。

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

dist[u] != INF のチェックは、まだ到達していないノードから出る辺を読み飛ばします。Pythonでは float("inf") + w も無限大のままなので、主に無駄な処理を省く役割です。無限大に大きな整数を使う言語では、オーバーフローや誤った更新を防ぎます。

時間計算量と空間計算量

1,000ノード・10,000辺のグラフでは最大で約1,000万回の緩和になるため、重みがすべて非負ならダイクストラ法のほうがずっと高速です。

バリエーションとよくある間違い

• 早期終了：1回分の全辺の処理で何も変わらなければ停止します。安全であり、実際にはかなり高速になることが多い方法です。
• SPFA（Shortest Path Faster Algorithm）：キューを使い、距離が変わったノードから出る辺だけを再度緩和します。多くの場合高速ですが、最悪計算量は同じ O(V × E) です。
• ホップ数制限付き経路：前の回の距離のコピーを使ってちょうど k 回実行すると、辺が高々 k 本の最安経路が求まります。「経由 k 回以内で最安の航空券」を解くことができます。
• 閉路そのものの特定：親の対応表を保持しておき、追加の1回でノード v が更新されたら、親を V 回たどって閉路の内側に入り、同じノードに戻るまでたどります。

使う場面と実世界での用途

• 辺の重みが負になりうる場合や、負閉路を検出する必要がある場合にベルマン–フォード法を使います。それ以外はダイクストラ法を優先してください。
• RIPなどの距離ベクトル型ルーティングプロトコルは、分散型のベルマン–フォード法の考え方を使っています。各ルーターが、隣接ルーターの推定値をもとに自分の距離の推定値を繰り返し更新します。
• 通貨の裁定取引：重みを -log(rate) にすると、負閉路は、交換を繰り返すと元より多くのお金が手に入る取引の列に対応します。
• ジョンソン法は、ベルマン–フォード法を1回実行してグラフの重みを付け替え、その後、全ノードからダイクストラ法を使って全点対最短経路を求めます。
• 差分制約（x - y <= c のような不等式の系）は最短経路として解けます。負閉路があるなら解は存在しません。