重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズム[1]の一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。(中略)他の問題を最短経路問題に還元すると、自然に負の重みが現れる」[2]。負閉路を含むグラフとしよう。おける辺の重複を許さない(負閉路を含む)最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。回繰り返す(初期状態で始点以外の頂点の始点からの距離は無限大にしておき、処理の途中段階で各頂点の始点からの最短距離と思われる距離に置き換えていく。relaxing(=「緩める」「緩和」など)と称する)。負の閉路がなければ最短経路上の各頂点は高々1回しか出現しないので、反復によって最短距離が正確にグラフ全体に伝播する。重みが正であることを前提とした構造上の仮定に基づく貪欲法的手法とは異なり、この直接的な方法はより汎用的である。|V|と|E|はそれぞれ頂点数と辺数である。この実装では、グラフを頂点のリストと辺のリストで表す。最短経路を格納するよう変更していく。cycle"正しさの証明[編集]このアルゴリズムの正しさは数学的帰納法で示すことができる。何らかの経路の距離と等しい。最短経路の距離である。サイクルを実行する前の時点を考える。