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

辺の長さはすべて正なので、ダイクストラ法で頂点 $1$ からの最短距離 $d(v)$ を求め、同時に最短路の本数 $c(v)$ を数える。最短路の本数は、$d(v)=d(u)+w(u\to v)$ を満たす直前の頂点 $u$ すべてについて $c(u)$ を足し合わせれば得られる（最短路の部分経路も最短路であるため）。

• 頂点 $1$：$d(1)=0$, $c(1)=1$。
• 頂点 $3$：候補は $1\to 3$ の $2$ のみ。$d(3)=2$, $c(3)=1$。
• 頂点 $2$：候補は $1\to 2$ で $0+3=3$、$3\to 2$ で $2+1=3$。どちらも $3$ なので $d(2)=3$, $c(2)=c(1)+c(3)=2$。
• 頂点 $4$：候補は $1\to 4$ で $6$、$2\to 4$ で $3+2=5$、$3\to 4$ で $2+3=5$。$d(4)=5$, $c(4)=c(2)+c(3)=2+1=3$。
• 頂点 $5$：候補は $2\to 5$ で $3+5=8$、$4\to 5$ で $5+2=7$。$d(5)=7$, $c(5)=c(4)=3$。
• 頂点 $6$：候補は $3\to 6$ で $2+7=9$、$2\to 6$ で $3+6=9$、$4\to 6$ で $5+3=8$。$d(6)=8$, $c(6)=c(4)=3$。
• 頂点 $7$：候補は $5\to 7$ で $7+3=10$、$6\to 7$ で $8+2=10$。どちらも $10$ なので $d(7)=10$, $c(7)=c(5)+c(6)=3+3=6$。

具体的には、頂点 $4$ までの最短路 $1\to 2\to 4$, $1\to 3\to 2\to 4$, $1\to 3\to 4$（いずれも長さ $5$）の 3 本それぞれに、$4\to 5\to 7$ または $4\to 6\to 7$（いずれも長さ $5$）をつないだ $3\times 2=6$ 本である。

したがって $(L,N)=(10,6)$。

グラフは閉路を持たない(辺は 1→2,1→3,1→4,3→2,2→4,3→4,2→5,2→6,3→6,4→5,4→6,5→7,6→7 で、順序 1,3,2,4,5,6,7 に沿う)。この順に最短距離 $d$ と最短路の本数 $n$ を求める。

$d_1=0,n_1=1$。
$d_3=2$(1→3)、$n_3=1$。
$d_2=\min (3,2+1)=3$、両方が最短なので $n_2=2$。
$d_4=\min (6,d_2+2=5,d_3+3=5)=5$、$n_4=n_2+n_3=3$。
$d_5=\min (d_2+5=8,d_4+2=7)=7$、$n_5=n_4=3$。
$d_6=\min (d_2+6=9,d_3+7=9,d_4+3=8)=8$、$n_6=n_4=3$。
$d_7=\min (d_5+3=10,d_6+2=10)=10$、$n_7=n_5+n_6=6$。

長さがちょうど最短の $L$ である経路は最短路そのものなので $N=6$。検算:経路 1→2→4→5→7、1→3→4→5→7、1→3→2→4→5→7 の長さはそれぞれ 3+2+2+3=10、2+3+2+3=10、2+1+2+2+3=10 で、6 経由も同様に 3 本、計 6 本。

よって $(L,N)=(10,6)$。