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

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

辺の長さはすべて正なので、$s$ に近い頂点から順に最短距離を確定できる（緩和 $d(v)\leftarrow \min (d(v),d(u)+\ell (u,v))$ をくり返しても同じ結果になる）。

• $d(s)=0$
• $d(a)=\min (0+2)=2$（$b$ 経由は $3+1=4$ で長い）
• $d(b)=\min (0+3,2+1)=3$
• $d(c)=\min (2+3,3+2)=5$
• $d(d)=\min (3+4,5+1)=6$
• $d(t)=\min (5+4,6+3)=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$ ○
• $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$

（確認：長さ $9$ の路は $s\text{-}a\text{-}c\text{-}t$、$s\text{-}b\text{-}c\text{-}t$、$s\text{-}a\text{-}b\text{-}c\text{-}t$、$s\text{-}a\text{-}c\text{-}d\text{-}t$、$s\text{-}b\text{-}c\text{-}d\text{-}t$、$s\text{-}a\text{-}b\text{-}c\text{-}d\text{-}t$ の $6$ 本である。）

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

$s$ から各頂点への最短距離と最短路の本数を、ダイクストラ法の考え方で順に求める。

• $s$: 距離 0、本数 1。
• $a$: 距離は $s$—$a$ の 2。$b$ 経由は $3+1=4$ なので長い。本数 1。
• $b$: 直接 $s$—$b$ で 3、$a$ 経由 $s$—$a$—$b$ で $2+1=3$。ともに 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 本を列挙する。
1. $s,a,c,t$
2. $s,b,c,t$
3. $s,a,b,c,t$
4. $s,a,c,d,t$
5. $s,b,c,d,t$
6. $s,a,b,c,d,t$

どれも長さは 9 である。

答え: 6 本