ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム^[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。

グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。

ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」^[2]。G を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、G における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。

ベルマン–フォード法の基本構造はダイクストラ法とよく似ているが、ダイクストラ法が総当り的に未処理の重みが最小のノードを選択して緩めるのに対して、ベルマン–フォード法は頂点数を |V|としたとき、全辺を緩めることを単に|V| − 1 回繰り返す（初期状態で始点以外の頂点の始点からの距離は無限大にしておき、処理の途中段階で各頂点の始点からの最短距離と思われる距離に置き換えていく。これを relaxing（=「緩める」「緩和」など）と称する。負の閉路がなければ最短経路上の各頂点は高々1回しか出現しないので、反復によって最短距離が正確にグラフ全体に伝播する。重みが正であることを前提とした構造上の仮定に基づく貪欲法的手法とは異なり、この直接的な方法はより汎用的である。

ベルマン–フォード法の実行時間は O(|V|·|E|) で、|V|と|E|はそれぞれ頂点数と辺数である。

procedure BellmanFord(list vertices, list edges, vertex source)
   // この実装では、グラフを頂点のリストと辺のリストで表す。
   // そして、各頂点の distance と predecessor 属性が
   // 最短経路を格納するよう変更していく。

   // Step 1: グラフの初期化
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null
   
   // Step 2: 辺の緩和を反復
   for i from 1 to size(vertices) - 1:       
       for each edge uv in edges: // uv は u から v に向かう辺
           u := uv.source
           v := uv.destination             
           if v.distance > u.distance + uv.weight:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: 負の重みの閉路がないかチェック
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           error "Graph contains a negative-weight cycle"

このアルゴリズムの正しさは数学的帰納法で示すことができる。以下にそれを示す。

補題: for サイクルを i 回繰り返したとき:

• Distance(u) が無限大でないとき、その値は s から u の何らかの経路の距離と等しい。
• 高々 i 個の辺からなる s から u への経路があるとき、Distance(u) は高々 i 個の辺から成る s から u への高々最短経路の距離である。

証明: 帰納法の基本ケースとして、i=0 で for サイクルを実行する前の時点を考える。すると、始点については source.distance = 0 であるから正しい。他の頂点 u については u.distance = infinity なので、これも正しい（0個の辺からなる始点から u への経路は存在しない）。

帰納ケースについては、まず第1の部分を証明する。ある頂点の距離が v.distance := u.distance + uv.weight で更新された時点を考える。帰納法上の前提により、u.distance は始点から u へのなんらかの経路の距離である。したがって u.distance + uv.weight は始点から u までの経路の長さと、そこから v までの距離を加えたもので、始点から v までの経路の距離である。

第2の部分については、高々 i 個の辺からなる始点から u への最短経路を考える。v が その経路上 u の直前の頂点だとする。すると、始点から v までの経路は高々 i-1 個の辺からなる始点から v までの最短経路となる。帰納法上の前提により、i-1 回の反復後の v.distance は高々この経路の距離である。したがって、uv.weight + v.distance は高々 s から u への経路の距離である。i-番目の反復で、u.distance は uv.weight + v.distance と比較され、uv.weight + v.distance の方が小さければその値が設定される。したがって、i 回の反復後、u.distance は高々始点から uへの最短経路の距離であり、その経路には高々 i 個の辺がある。

負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。したがって step 3 に至ったとき、それ以上の経路や距離の短縮は不可能である。逆に短縮できないとすると、頂点 v[0],..,v[k-1] の任意の閉路について、次が成り立つ。

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

閉路上で総和を求めると、v[i].distance の項と v[i-1 (mod k)].distance の項は相殺され、次の式が残る。

0 <= v[i-1 (mod k)]v[i].weight の 1 から k までの総和

すなわち、全ての閉路は負でない重みを持つ。

ベルマン-フォード法の分散版は、Routing Information Protocol (RIP) などの距離ベクトル型ルーティングプロトコルで使われている。分散版にするのは、典型的にはISPが保有するIPネットワーク群の集合体のように、自律システム (AS) 内の複数のノード（ルーター）が関与するためである。これは次のステップで構成される。

1. 各ノードは自身とAS内の他の全ノードとの距離を計算し、その情報をテーブルに格納する。
2. 各ノードはそのテーブルを隣接する全ノードに送る。
3. 隣接ノードから距離テーブルを受け取ると、他の全ノードへの最短経路を計算し、自身のテーブルを適宜更新する。

このときのベルマン-フォード法の主な欠点は次の通りである。

• スケーラビリティが良くない。
• ネットワーク構成に変更があった場合、ノードからノードへと伝達されるため、すぐには反映されない。
• 無限に数えてしまう（リンクやノードの障害によって、他のノードから到達不能なノードが生じた場合、到達できない部分への推定距離を増大させる処理が無限に続く可能性があり、その間ルーティング上のループが生じ得る）。

1970年、Yenはベルマン-フォード法の改良を発表した^[3]。Yenの改良は、まず全頂点に何らかの線型な順序を割り当て、全辺の集合を2つの部分集合に分割する。第1の部分集合 E_f は i < j となる全ての辺 (v_i, v_j) を含み、第2の部分集合 E_b は i > j となる辺 (v_i, v_j) を含む。そして頂点を v₁, v₂,...,v_|V| の順に見ていき、その頂点から出ている E_f 内の辺を緩和させる。次に v_|V|, v_|V|-1,...,v₁ という順序で頂点を見ていき、その頂点から出ている E_b 内の辺を緩和させる。Yenの改良は単一始点の最短経路問題で調べる必要のある経路数を事実上半減させる。

• Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-90, 1958.
• L. R. Ford, Jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, 1962.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman-Ford algorithm, pp.588–592. Problem 24-1, pp.614–615.

• 対話型Javaアプレットによるデモ
• Cのコード例
• annas オープンソースのJava用グラフパッケージ。ベルマン-フォード法もある。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版） 有効制約法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）