グラフ理論の問題

ベルマン・フォード法では、はじめに $d(s)=0$、それ以外の頂点を $d(v)=\infty$ とおき、すべての辺 $(u,v,w)$ について緩和
$$d(v)\leftarrow \min (d(v),d(u)+w)$$
を行う操作を $|V|-1=3$ 回くり返す。ここでは辺を問題文の順に調べる。

初期値：$d(s)=0,d(a)=d(b)=d(c)=\infty$。

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

1 回目の終わりで $d(a)=5,d(b)=1,d(c)=3$。

2 回目
- $(s,a,5)$：$0+5=5$ は $d(a)=5$ より小さくないので変化なし。
- $(s,b,3)$：$0+3=3>1$ で変化なし。
- $(a,b,-4)$：$5-4=1$ で変化なし。
- $(a,c,4)$：$5+4=9>3$ で変化なし。
- $(b,c,2)$：$1+2=3$ で変化なし。

2 回目で値が 1 つも変わらなかったので、3 回目も変化しない。さらにもう 1 回すべての辺を調べても更新が起きないので、このグラフには負の閉路がなく、得られた値が最短距離である。

実際、$d(b)=1$ は経路 $s\to a\to b$（$5+(-4)=1$）、$d(c)=3$ は経路 $s\to a\to b\to c$（$5-4+2=3$）で実現されている。負の辺 $(a,b,-4)$ を通ることで、直接の辺 $s\to b$（重み 3）より短くなっている点に注意する。

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

s から各頂点への経路を列挙する。
a への経路は s→a のみで、長さは 5 なので $d(a)=5$。
b への経路は s→b（長さ 3）と s→a→b（長さ $5-4=1$）の 2 通りで、最小は 1 なので $d(b)=1$。
c への経路は s→a→c（長さ 9）、s→b→c（長さ 5）、s→a→b→c（長さ $5-4+2=3$）の 3 通りで、最小は 3 なので $d(c)=3$。

ベルマン・フォード法による確認。初期値は $d(s)=0$、他は $\infty$ とし、辺を問題文に書かれた順に緩和する。
1 回目: (s,a) で $d(a)=5$、(s,b) で $d(b)=3$、(a,b) で $5-4=1<3$ より $d(b)=1$、(a,c) で $d(c)=9$、(b,c) で $1+2=3<9$ より $d(c)=3$。
2 回目: どの辺を緩和しても値は更新されず、収束する。負閉路もない（グラフは非巡回）。

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