グラフ理論の問題

初期化　$d(s)=0,d(a)=d(b)=d(c)=\infty$ とする。

辺を $(s,a),(s,b),(a,b),(a,c),(b,c)$ の順に調べ、各辺 $(u,v)$ について緩和
$$d(v)\leftarrow \min (d(v),d(u)+w(u,v))$$
を行う。これを $|V|-1=3$ 回くり返す。

1 回目
- $(s,a)$: $d(a)=\min (\infty ,0+4)=4$
- $(s,b)$: $d(b)=\min (\infty ,0+2)=2$
- $(a,b)$: $d(b)=\min (2,4+(-3))=1$
- $(a,c)$: $d(c)=\min (\infty ,4+5)=9$
- $(b,c)$: $d(c)=\min (9,1+3)=4$

この時点で $d(a)=4,d(b)=1,d(c)=4$。

2 回目
- $(s,a)$: $\min (4,4)=4$
- $(s,b)$: $\min (1,2)=1$
- $(a,b)$: $\min (1,1)=1$
- $(a,c)$: $\min (4,9)=4$
- $(b,c)$: $\min (4,4)=4$

どの値も変わらない。3 回目も同じ計算になり、値は変わらない。

負の閉路の判定　$|V|-1$ 回の後にもう一度すべての辺を調べても更新が起きないので、$s$ から到達できる負の閉路はない。したがって得られた値が最短距離である。

実際、最短路は $s\to a$（距離 $4$）、$s\to a\to b$（$4-3=1$）、$s\to a\to b\to c$（$1+3=4$）である。なお、負の重みがあるためダイクストラ法では $b$ を距離 $2$ で確定してしまい正しく求められないが、ベルマン・フォード法では正しく求まる。

よって $(d(a),d(b),d(c))=(4,1,4)$。

始点 $s$ から各頂点への最短距離をベルマン・フォード法で求める。初期値は $d(s)=0$、$d(a)=d(b)=d(c)=\infty$。

1回目の緩和（辺の順は $(s,a),(s,b),(a,b),(a,c),(b,c)$）:
- $(s,a)$: $d(a)=4$
- $(s,b)$: $d(b)=2$
- $(a,b)$: $4-3=1<2$ より $d(b)=1$
- $(a,c)$: $4+5=9$ より $d(c)=9$
- $(b,c)$: $1+3=4<9$ より $d(c)=4$

2回目の緩和ではどの値も更新されないので、収束している。負の閉路もない（グラフは非巡回）。

検算: $s\to a$ の道は $s\to a$ のみで長さ 4。$s\to b$ の道は $s\to b$（2）と $s\to a\to b$（$4-3=1$）なので最短は 1。$s\to c$ の道は $s\to a\to c$（9）、$s\to b\to c$（5）、$s\to a\to b\to c$（$4-3+3=4$）なので最短は 4。

よって $(d(a),d(b),d(c))=(4,1,4)$。