オペレーションズ・リサーチの問題

手順 1：最短距離 $d(v)$ を求める。

すべての道路の長さは正なので、$S$ に近い順に確定させていけばよい（ベルマン・フォード法の緩和 $d(v)\leftarrow \min (d(v),d(u)+\ell (u,v))$ をくり返しても同じ結果になる）。

• $d(S)=0$
• $d(A)=\min (0+2,d(B)+1)=2$
• $d(B)=\min (0+3,2+1)=3$
• $d(C)=\min (d(A)+3,d(B)+2)=\min (5,5)=5$
• $d(D)=\min (d(B)+4,d(C)+1)=\min (7,6)=6$
• $d(T)=\min (d(C)+4,d(D)+3)=\min (9,9)=9$

手順 2：$d(u)+\ell (u,v)=d(v)$ を満たす向きの辺だけを残す。

• $S\to A$：$0+2=2$ ○　（$B\to A$：$3+1=4\ne 2$ ×）
• $S\to B$：$0+3=3$ ○、$A\to B$：$2+1=3$ ○
• $A\to C$：$2+3=5$ ○、$B\to C$：$3+2=5$ ○
• $C\to D$：$5+1=6$ ○、$B\to D$：$3+4=7\ne 6$ ×
• $C\to T$：$5+4=9$ ○、$D\to T$：$6+3=9$ ○

手順 3：$N(v)={\sum }_{u}N(u)$ を $d$ の小さい順に足し合わせる。（和は手順 2 で残った辺 $u\to v$ についてとる）

• $N(S)=1$
• $N(A)=N(S)=1$
• $N(B)=N(S)+N(A)=1+1=2$
• $N(C)=N(A)+N(B)=1+2=3$
• $N(D)=N(C)=3$
• $N(T)=N(C)+N(D)=3+3=6$

（確認：$S$ から $C$ への最短路は $S-A-C$, $S-B-C$, $S-A-B-C$ の 3 通りで、そのそれぞれに $C-T$ または $C-D-T$ をつなぐので $3\times 2=6$ 通り。長さはいずれも $9$ km。）

よって、最短路は $6$ 通りである。

$S$ からの最短距離を求める。$d(S)=0$、$d(A)=2$、$d(B)=\min (3,2+1)=3$、$d(C)=\min (d(A)+3,d(B)+2)=5$、$d(D)=\min (d(C)+1,d(B)+4)=\min (6,7)=6$、$d(T)=\min (d(C)+4,d(D)+3)=\min (9,9)=9$。よって最短距離は 9 km。

最短路の本数 $N(X)$ を、最短距離を実現する辺だけをたどって数える。
- $N(S)=1$
- $N(A)=1$（$S$–$A$ のみ。$S$–$B$–$A$ は $3+1=4>2$ なので不可）
- $N(B)=N(S)+N(A)=2$（$S$–$B$ は $3$、$S$–$A$–$B$ は $2+1=3$）
- $N(C)=N(A)+N(B)=1+2=3$（$A$ から $2+3=5$、$B$ から $3+2=5$）
- $N(D)=N(C)=3$（$C$ 経由は $5+1=6$。$B$ 経由は $3+4=7$ で不可）
- $N(T)=N(C)+N(D)=3+3=6$（$C$ 経由は $5+4=9$、$D$ 経由は $6+3=9$）

検算として 6 本を書き出す。
- $S$-$A$-$C$-$T$：$2+3+4=9$
- $S$-$B$-$C$-$T$：$3+2+4=9$
- $S$-$A$-$B$-$C$-$T$：$2+1+2+4=9$
- $S$-$A$-$C$-$D$-$T$：$2+3+1+3=9$
- $S$-$B$-$C$-$D$-$T$：$3+2+1+3=9$
- $S$-$A$-$B$-$C$-$D$-$T$：$2+1+2+1+3=9$

どれも長さ 9 で、上の漸化式の結果と一致する。したがって答えは 6 通り。