ベルマン–フォード法

ベルマン–フォード法 () は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと にちなむ。
グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。
ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」。"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" 回繰り返したとき:
証明: 帰納法の基本ケースとして、codice_1 で "for" サイクルを実行する前の時点を考える。すると、始点については codice_2 であるから正しい。他の頂点 "u" については codice_3 なので、これも正しい（0個の辺からなる始点から "u" への経路は存在しない）。
帰納ケースについては、まず第1の部分を証明する。ある頂点の距離が codice_4 で更新された時点を考える。帰納法上の前提により、codice_5 は始点から "u" へのなんらかの経路の距離である。したがって codice_6 は始点から "u" までの経路の長さと、そこから "v" までの距離を加えたもので、始点から "v" までの経路の距離である。
第2の部分については、高々 "i" 個の辺からなる始点から "u" への最短経路を考える。"v" が その経路上 "u" の直前の頂点だとする。すると、始点から "v" までの経路は高々 "i-1" 個の辺からなる始点から "v" までの最短経路となる。帰納法上の前提により、"i-1" 回の反復後の codice_7 は高々この経路の距離である。したがって、codice_8 は高々 "s" から "u" への経路の距離である。"i"-番目の反復で、codice_5 は codice_8 と比較され、codice_8 の方が小さければその値が設定される。したがって、"i" 回の反復後、codice_5 は高々始点から "u"への最短経路の距離であり、その経路には高々 "i" 個の辺がある。
負の重みの閉路がないなら、それぞれの最短経路には各頂点は高々1回出現する。したがって step 3 に至ったとき、それ以上の経路や距離の短縮は不可能である。逆に短縮できないとすると、頂点 v[0]..,v[k-1] の任意の閉路について、次が成り立つ。
codice_13
閉路上で総和を求めると、v[i].distance の項と v[i-1 (mod k)].distance の項は相殺され、次の式が残る。
codice_14
すなわち、全ての閉路は負でない重みを持つ。
応用.
ベルマン-フォード法の分散版は、Routing Information Protocol (RIP) などの距離ベクトル型ルーティングプロトコルで使われている。分散版にするのは、典型的にはISPが保有するIPネットワーク群の集合体のように、自律システム (AS) 内の複数のノード（ルーター）が関与するためである。これは次のステップで構成される。
このときのベルマン-フォード法の主な欠点は次の通りである。
Yenによる改良.
1970年、Yenはベルマン-フォード法の改良を発表した。Yenの改良は、まず全頂点に何らかの線型な順序を割り当て、全辺の集合を2つの部分集合に分割する。第1の部分集合 Ef は i < j となる全ての辺 (vi, vj) を含み、第2の部分集合 Eb は i > j となる辺 (vi, vj) を含む。そして頂点を v1, v2...,v|V| の順に見ていき、その頂点から出ている Ef 内の辺を緩和させる。次に v|V|, v|V|-1...,v1 という順序で頂点を見ていき、その頂点から出ている Eb 内の辺を緩和させる。Yenの改良は単一始点の最短経路問題で調べる必要のある経路数を事実上半減させる。