グラフ理論の問題

ベルマン・フォード法では、初期値を $d(s)=0$、$d(a)=d(b)=d(c)=\infty$ とする。すべての辺 $(u,v)$ について緩和
$$d(v)\leftarrow \min (d(v),d(u)+w(u,v))$$
を行う操作を 1 回とし、これを $|V|-1=3$ 回くり返す。辺は問題文の順に調べる。

1 回目
- $s\to a$：$\min (\infty ,0+2)=2$ なので $d(a)=2$。
- $s\to b$：$\min (\infty ,0+5)=5$ なので $d(b)=5$。
- $b\to a$：$\min (2,5+(-4))=\min (2,1)=1$ なので $d(a)=1$（負の辺によって距離が短くなる）。
- $a\to c$：$\min (\infty ,1+3)=4$ なので $d(c)=4$。
- $b\to c$：$\min (4,5+1)=4$ で変化なし。
- $c\to b$：$\min (5,4+2)=5$ で変化なし。

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

2 回目
- $s\to a$：$\min (1,2)=1$、$s\to b$：$\min (5,5)=5$、$b\to a$：$\min (1,1)=1$、$a\to c$：$\min (4,4)=4$、$b\to c$：$\min (4,6)=4$、$c\to b$：$\min (5,6)=5$。
どの値も変化しない。

3 回目 も 2 回目と同じ計算になり、変化はない。

さらにもう 1 回（4 回目）すべての辺を調べても更新は起こらないので、負の閉路がないことも確認できる。実際、$s$ に入る辺はなく、$a$ に入る辺は $s\to a$ と $b\to a$ だけなので、このグラフの閉路は $b\to a\to c\to b$（重み $-4+3+2=1$）と $b\to c\to b$（重み $1+2=3$）の 2 つであり、いずれも重みは正である。

よって最短距離は $d(a)=1$（経路 $s\to b\to a$）、$d(b)=5$（経路 $s\to b$）、$d(c)=4$（経路 $s\to b\to a\to c$）であり、答えは $(1,5,4)$ である。

辺は s→a:2, s→b:5, b→a:-4, a→c:3, b→c:1, c→b:2。

負の閉路がないか確認する。閉路は b→c→b だけで、重みは 1+2=3>0 なので負の閉路はない。

ベルマン・フォード法を行う。初期値は d(s)=0、d(a)=d(b)=d(c)=∞ とする。辺の緩和は問題文に書かれた順に行う。

1 回目: s→a で d(a)=2。s→b で d(b)=5。b→a で 5-4=1<2 なので d(a)=1。a→c で 1+3=4 なので d(c)=4。b→c は 5+1=6 で、4 より大きいので更新しない。c→b は 4+2=6 で、5 より大きいので更新しない。

2 回目: 更新される値はない。よって収束する。

結果は d(a)=1, d(b)=5, d(c)=4 である。

検算: a への経路は s→b→a で 5-4=1、直接の s→a では 2 なので 1 が最短。b への経路は s→b で 5。s→a→c→b は 2+3+2=7、s→b→a→c→b は 1+3+2=6 で、いずれも 5 より長い。c への経路は s→b→a→c で 5-4+3=4、s→b→c では 6 なので 4 が最短。

よって (d(a), d(b), d(c)) = (1, 5, 4) である。