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

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

辺の長さはすべて正なので、$S$ に近い頂点から順に決めていける。

• $d(S)=0$
• $d(A)=\min \{0+2,d(B)+1\}=2$（$S$ から直接）
• $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$ ○
• $S\to B$：$0+3=3$ ○
• $A\to B$：$2+1=3$ ○
• $A\to C$：$2+3=5$ ○
• $B\to C$：$3+2=5$ ○
• $B\to D$：$3+4=7\ne 6$ ×
• $C\to D$：$5+1=6$ ○
• $C\to T$：$5+4=9$ ○
• $D\to T$：$6+3=9$ ○

（逆向き、たとえば $B\to A$ は $3+1=4\ne 2$ なので残らない。他の逆向きも同様に残らない。）

手順 3：$N(v)={\sum }_{u}N(u)$ を始点から順に足す。

残した辺で $v$ に入ってくる辺の始点 $u$ について $N(u)$ を足し合わせる。

• $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$

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

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

S からの最短距離を求め、最短路の本数を数える。

• $d(S)=0$、本数 1。
• $A$: $S$–$A$ で 2。本数 1。
• $B$: $S$–$B$ で 3、$S$–$A$–$B$ で $2+1=3$。距離 3、本数 2。
• $C$: $A$ 経由は $2+3=5$、$B$ 経由は $3+2=5$。距離 5。本数は $1+2=3$。
• $D$: $C$ 経由は $5+1=6$、$B$ 経由は $3+4=7$。距離 6。本数は $C$ 経由の 3。
• $T$: $C$ 経由は $5+4=9$、$D$ 経由は $6+3=9$。距離 9。本数は $3+3=6$。

辺の長さは正なので、最短路は同じ頂点を二度通らない。

検算として 6 本を列挙する。$S\text{-}A\text{-}C\text{-}T$、$S\text{-}A\text{-}B\text{-}C\text{-}T$、$S\text{-}B\text{-}C\text{-}T$、$S\text{-}A\text{-}C\text{-}D\text{-}T$、$S\text{-}A\text{-}B\text{-}C\text{-}D\text{-}T$、$S\text{-}B\text{-}C\text{-}D\text{-}T$。長さはいずれも 9 である。

答えは 6 本。