最短路の本数の数え上げ

始点から各頂点への最短距離 $d (v)$ の表を作り、 $d (u) + ℓ (u, v) = d (v)$ を満たす辺だけを残して、 $N (v) = \sum_{u} N (u)$ を始点から順に足し合わせ、最短路の本数を数えられる

前提

和の法則・積の法則と樹形図（数学A 場合の数と確率）
負の重みを含む最短路（ベルマン・フォード法）（大学数学グラフ理論）

この技能までの道筋（4 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
負の重みを含む最短路（ベルマン・フォード法）（大学数学グラフ理論）

説明

重み（長さ）付きの有向グラフで、始点 $s$ から終点 $t$ への最短路が何本あるかを数える方法です。経路をすべて書き出す必要はありません。手順は三つに分かれます。まず各頂点への最短距離 $d (v)$ の表を作り、次に最短路に使われうる辺だけを残し、最後に始点から順に本数を足し合わせます。道路網で最短ルートが何通りあるかを調べるときや、最短路がただ 1 本に決まるかを確かめるときに使います。

なぜそうしてよいのか

このページでは、経路を歩道として扱います。歩道とは、同じ頂点や辺を何度通ってもよい辺の並びのことです。辺の長さの合計が最小の歩道を最短路と呼び、その長さを $d (v)$ 、本数を $N (v)$ と書きます。始点から到達できる負の閉路はないものとします（ベルマン・フォード法で確かめます）。 $d (v) = \infty$ の頂点は到達できないので無視します。

$v$ への最短路の最後の辺を $u \to v$ （長さ $ℓ (u, v)$ ）とします。この辺を除いた前半は $u$ への歩道で、長さは $d (v) - ℓ (u, v)$ です。仮にこれが $d (u)$ より長いとすると、前半を $u$ への最短路に取り替えたとき、 $v$ への歩道が $d (v)$ より短くなってしまいます。これは矛盾なので、前半は $u$ への最短路で、 $d (u) + ℓ (u, v) = d (v)$ が成り立ちます。逆に、この等式を満たす辺があれば、 $u$ への任意の最短路の後ろにこの辺をつなぐと、長さちょうど $d (v)$ の歩道、つまり最短路になります。この等式を満たす辺を「最短路の辺」と呼びます。すると $v$ への最短路は、最後に使う最短路の辺で重なりなく分けられます。最後の辺 $u \to v$ を 1 本決めると、その最短路は $u$ への最短路と 1 対 1 に対応し、ちょうど $N (u)$ 本あります。したがって和の法則から $N (v) = \sum N (u)$ です。和は $v$ に入る最短路の辺すべてにわたってとります。出発点は $N (s) = 1$ で、これは長さ 0 の、何も進まない歩道 1 本にあたります。

残る問題は計算の順番です。最短路の辺だけでできた閉路があれば、その上で等式 $d (u) + ℓ (u, v) = d (v)$ を一周分足し合わせることができます。左右の $d$ が打ち消し合うので、閉路の長さの合計は 0 になります。そのため、辺の長さがすべて正なら、そのような閉路はありません。最短路の辺 $u \to v$ では $d (u) < d (v)$ なので、 $d$ の小さい順に計算すれば、必要な $N (u)$ はいつも計算済みです。長さ 0 や負の辺があるときは、最短路の辺の中に長さ 0 の閉路ができることがあります。その閉路上の頂点 $w$ から最短路の辺をたどって $t$ に行けるなら、 $s \to w$ の最短路、閉路を $k$ 周、 $w \to t$ の最短路の辺をつないだ歩道は、どれも長さ $d (t)$ です（ $k = 0, 1, 2, \dots$ ）。よって $N (t)$ は無限になります。一方、 $t$ に至れない閉路は $t$ への最短路には現れません。 $t$ への最短路に現れる頂点は、そこから最短路の辺で $t$ に至れるものだけだからです。そこで、最短路の辺で $t$ に至れる頂点だけを残します。その部分に閉路がなければ、各辺 $u \to v$ で $u$ が $v$ より先に来る並べ方（位相順）がとれます。この順に計算すれば $N (t)$ は有限の値として求まります。

手順

最短距離の表を作る：ベルマン・フォード法で始点 $s$ から各頂点への $d (v)$ を求め、負の閉路がないことを確かめる（辺の長さがすべて正の場合も同じ方法でよい）。 $d (v) = \infty$ の頂点は捨てる。
最短路の辺を選ぶ：すべての辺 $u \to v$ について $d (u) + ℓ (u, v) = d (v)$ が成り立つか調べ、成り立つ辺だけを残す。
閉路を調べて計算順を決める：残した辺をたどって $t$ に至れる頂点だけを残す。その中に閉路があれば、最短路は無限に多いので終了する。閉路がなければ、残した各辺 $u \to v$ で $u$ が $v$ より先に来る順（位相順）に頂点を並べる。辺の長さがすべて正なら、 $d$ の小さい順がそのような順になる。
初期値を置いて順に足す： $N (s) = 1$ とし、決めた順に $N (v) = \sum N (u)$ を計算する。和は、残した辺 $u \to v$ すべてにわたってとる。同じ $u$ から $v$ への残った辺が複数あれば、その本数だけ $N (u)$ を足す。
答えを読む： $N (t)$ が $s$ から $t$ への最短路の本数である。

例題

頂点 $s, a, b, c, t$ をもつ有向グラフがあり、辺とその長さは次のとおりである： $s \to a (1)$ , $s \to b (2)$ , $a \to b (1)$ , $a \to c (3)$ , $b \to c (2)$ , $b \to t (4)$ , $c \to t (1)$ , $a \to t (5)$ 。 $s$ から $t$ への最短路の本数を求めよ。

例題の解答

手順1（最短距離の表）：ベルマン・フォード法を使います。初期値は $d (s) = 0$ 、他の頂点はすべて $\infty$ です。問題文の辺の順に緩和します。
1 周目：
- $s \to a$ で $d (a) = 1$ 、 $s \to b$ で $d (b) = 2$
- $a \to b$ ： $1 + 1 = 2$ で変化なし
- $a \to c$ で $d (c) = 4$ 。 $b \to c$ ： $2 + 2 = 4$ で変化なし
- $b \to t$ で $d (t) = 6$ 。 $c \to t$ ： $4 + 1 = 5$ なので $d (t) = 5$
- $a \to t$ ： $1 + 5 = 6$ で変化なし

2 周目はどの値も変わりません。1 周で変化がなければ、それ以降も変わりません。よって $d (s) = 0, d (a) = 1, d (b) = 2, d (c) = 4, d (t) = 5$ です。負の閉路はありません（さらに 1 周しても値が変わらないため）。

手順2（最短路の辺）：
- $s \to a$ （ $0 + 1 = 1$ ）、 $s \to b$ （ $0 + 2 = 2$ ）、 $a \to b$ （ $1 + 1 = 2$ ）は成立
- $a \to c$ （ $1 + 3 = 4$ ）、 $b \to c$ （ $2 + 2 = 4$ ）、 $c \to t$ （ $4 + 1 = 5$ ）も成立
- $b \to t$ （ $2 + 4 = 6 \neq = 5$ ）と $a \to t$ （ $1 + 5 = 6 \neq = 5$ ）は捨てる

手順3（閉路と計算順）：残した辺で、どの頂点からも $t$ に至れます。辺の長さはすべて正なので閉路はありません。 $d$ の小さい順 $s, a, b, c, t$ で計算します。

手順4（順に足す）： $N (s) = 1$ から始めます。
- $N (a) = N (s) = 1$
- $N (b) = N (s) + N (a) = 2$
- $N (c) = N (a) + N (b) = 3$
- $N (t) = N (c) = 3$

手順5：最短路は 3 本です。実際、 $s \to a \to c \to t$ 、 $s \to b \to c \to t$ 、 $s \to a \to b \to c \to t$ はどれも長さ 5 です。

答え: $3$

よくある誤り

$v$ に入るすべての辺について $N (u)$ を足してしまう誤り。例題で $N (t) = N (b) + N (c) + N (a) = 2 + 3 + 1 = 6$ とするのは誤りです。正しくは $d (u) + ℓ (u, v) = d (v)$ を満たす辺だけを足し、 $N (t) = N (c) = 3$ となります。
初期値を $N (s) = 0$ としてしまう誤り。こうすると全頂点で $N = 0$ になります。正しくは、長さ 0 の何も進まない歩道が 1 本あるので $N (s) = 1$ です。
長さ 0 や負の辺があるのに $d$ の順で計算してしまう誤り。辺 $s \to x (1)$ , $s \to y (1)$ , $x \to y (0)$ では $d (x) = d (y) = 1$ で、3 本とも最短路の辺です。ここで $y$ を $x$ より先に計算すると、まだ求まっていない $N (x)$ を使ってしまいます（ $N (x)$ を 0 として $N (y) = 1$ とするのは誤り）。正しくは位相順 $s, x, y$ で計算し、 $N (x) = 1$ 、 $N (y) = N (s) + N (x) = 2$ です。
最短路の辺からなる長さ 0 の閉路の扱いを誤る誤り。たとえば $x \to y (0)$ , $y \to x (0)$ が両方とも最短路の辺になったとします。 $x$ から最短路の辺で $t$ に至れるなら、この閉路を何周しても長さ $d (t)$ の歩道になるので、 $N (t)$ は有限になりません。これを見落として有限の値を答えるのは誤りです。逆に、その閉路から $t$ に至れないのに「無限」と答えるのも誤りです。正しくは、最短路の辺で $t$ に至れる頂点だけを残し、そこに閉路がなければ位相順に計算して有限の $N (t)$ を求めます。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

辺	長さ	辺	長さ	辺	長さ
$S$ – $A$	$2$	$A$ – $C$	$3$	$C$ – $D$	$1$
$S$ – $B$	$3$	$B$ – $C$	$2$	$C$ – $T$	$4$
$A$ – $B$	$1$	$B$ – $D$	$4$	$D$ – $T$	$3$

道路	長さ	道路	長さ	道路	長さ
$S$ – $A$	$2$	$A$ – $C$	$3$	$C$ – $D$	$1$
$S$ – $B$	$3$	$B$ – $C$	$2$	$C$ – $T$	$4$
$A$ – $B$	$1$	$B$ – $D$	$4$	$D$ – $T$	$3$

辺	長さ	辺	長さ	辺	長さ
$s$ — $a$	$2$	$a$ — $c$	$3$	$c$ — $d$	$1$
$s$ — $b$	$3$	$b$ — $c$	$2$	$c$ — $t$	$4$
$a$ — $b$	$1$	$b$ — $d$	$4$	$d$ — $t$	$3$

この技能を使う問題

難易度 3（期末試験の応用レベル）
頂点 $1, 2, \dots, 7$ からなる有向グラフがあり、各有向辺 $i \to j$ の長さ（正の整数）は次のとおりである。ここに書かれていない辺はない。
辺長さ辺長さ
$1 \to 2$ $3$ $3 \to 6$ $7$
$1 \to 3$ $2$ $2 \to 5$ $5$
$1 \to 4$ $6$ $2 \to 6$ $6$
$3 \to 2$ $1$ $4 \to 5$ $2$
$2 \to 4$ $2$ $4 \to 6$ $3$
$3 \to 4$ $3$ $5 \to 7$ $3$
$6 \to 7$ $2$
経路の長さを、通る辺の長さの和と定める。頂点 $1$ から頂点 $7$ への最短路の長さを $L$ 、長さがちょうど $L$ である頂点 $1$ から頂点 $7$ への経路の本数を $N$ とするとき、組 $(L, N)$ を求めよ。

辺	長さ	辺	長さ
$1 \to 2$	$3$	$3 \to 6$	$7$
$1 \to 3$	$2$	$2 \to 5$	$5$
$1 \to 4$	$6$	$2 \to 6$	$6$
$3 \to 2$	$1$	$4 \to 5$	$2$
$2 \to 4$	$2$	$4 \to 6$	$3$
$3 \to 4$	$3$	$5 \to 7$	$3$
		$6 \to 7$	$2$