負の重みを含む最短路（ベルマン・フォード法）

まず言葉を決めます。有向グラフとは、頂点の集合 $V$ と、向きのついた辺 $u\to v$ の集まりのことです。各辺には重み $w(u,v)$（負でもよい）がついています。辺を向きに沿ってたどったもの（同じ頂点を何度通ってもよい）を道とよび、その重みの合計を道の長さとします。始点 $s$ から頂点 $v$ への道の長さの最小値が最短距離です。同じ頂点に戻ってくる道で長さが負のものを負の閉路といいます。$s$ から負の閉路にたどり着けると、それを何周もすれば長さをいくらでも小さくできます。そのため、その閉路を経由して行ける頂点には最短距離が存在しません。

アルゴリズムでは、各頂点に「今わかっている最良の長さ」$d(v)$ を持たせます。最初は $d(s)=0$、ほかは $\infty$（まだ届いていない）とします。各辺 $u\to v$ について「$u$ まで長さ $d(u)$ で来られるなら、この辺を足せば $v$ へ $d(u)+w(u,v)$ で行ける」ので、$d(v)\leftarrow \min (d(v),d(u)+w(u,v))$ と書き換えます。これを緩和といいます。$d(v)$ は増えることがありません。また、有限の $d(v)$ はつねに $s$ から $v$ への実際の道の長さなので、最短距離より小さくなることはありません。すべての辺を 1 回ずつ緩和する作業を 1 巡とよびます。このとき「$k$ 巡したあとの $d(v)$ は、辺を $k$ 本以下使う $s$ から $v$ への道の長さの最小値以下」が成り立ちます（そのような道がなければ何も主張しません）。$k$ についての帰納法で示します。$k=0$ のとき、辺 0 本の道は $s$ にとどまる長さ 0 の道だけです。そして $d(s)=0$ なので成り立ちます。$k\ge 1$ のときは、辺 $k$ 本以下の道のうち最短のものを $P$ とします。$P$ の辺が $k-1$ 本以下なら、$k-1$ 巡目までに $d(v)$ はその長さ以下になっています。$d$ は増えないので、$k$ 巡目のあともそのままです。$P$ の辺がちょうど $k$ 本なら、最後の辺を $u\to v$ とします。$P$ のその手前までの部分は、辺 $k-1$ 本の $s$ から $u$ への道です。よって $k-1$ 巡目までに、$d(u)$ は有限で、その長さ以下になっています。$k$ 巡目にこの辺を緩和すると、$d(v)\le d(u)+w(u,v)\le$（$P$ の長さ）となります。

$s$ からたどり着ける負の閉路がなければ、$s$ から $v$ への最短の道は、同じ頂点を 2 度通らないものに取れます。道の途中の閉路は $s$ からたどり着けるので長さが 0 以上であり、取り除いても長さは増えないからです。このような道の辺は $|V|-1$ 本以下です。したがって $|V|-1$ 巡すれば、到達できるすべての $v$ で $d(v)$ が最短距離に一致します。到達できない $v$ は $\infty$ のままです。もう 1 巡しても何も変わりません。逆に、どの辺ももう緩和できない状態を考えます。このとき $s$ から到達できる頂点の $d$ はすべて有限です。$d(s)$ は有限です。そして $d(u)$ が有限で辺 $u\to v$ が緩和できないなら、$d(v)\le d(u)+w(u,v)$ なので $d(v)$ も有限です。これを $s$ からの道に沿ってくり返せばわかります。ここで、たどり着ける負の閉路 $v_0\to v_1\to \cdots \to v_k=v_0$ があったとします。閉路上の $d(v_i)$ はすべて有限なので、$d(v_i)\le d(v_{i-1})+w(v_{i-1},v_i)$ を $i=1,\dots ,k$ でたし合わせると、両辺の $d$ が打ち消し合います。その結果 $0\le$（閉路の重みの合計）となり、閉路の重みの合計が負であることに反します。よって、$|V|-1$ 巡のあとにまだ更新できる辺があることと、$s$ から到達できる負の閉路があることは同じです。