アルゴリズム設計解析特論第 1 回レポート

600p031-4 高木祐介

提出日 2000-05-16

6.4 図 6.38 の有向グラフに対し、

a b c d e f
a  3  4  5
b  1  1
c  2
d  3
e 3 2
f  2

(a) アルゴリズム Dijkstra を用いて、 a から他の頂点への最短経路を求めよ。

アルゴリズム Dijkstra を用いて、 S, w, D[v] を計算します。「最短経路を求めよ」とあるので、「最短経路で頂点 v の直前にある頂点」の配列 P [v] も計算し

ます。教科書どおりに、最初はすべての v ≠ a に対して P [v] = a に初期化します。そして、それまでに見つかっていた経路よりも短い、 w を通る経路を見つけたときに、 P [v] = w に更新します。

\begin{matrix}繰返し & S & w & D[b] & D[c] & D[d] & D[e] & D[f] & P [b] & P [c] & P [d] & P [e] & P [f] \\ 初期状態 & \{a\} & — & 3 & ∞ & 4 & ∞ & 5 & a & a & a & a & a \\ 1 & \{a, b\} & b & 3 & 4 & 4 & ∞ & 4 & a & b & a & a & b \\ 2 & \{a, b, c\} & c & 3 & 4 & 4 & ∞ & 4 & a & b & a & a & b \\ 3 & \{a, b, c, d\} & d & 3 & 4 & 4 & ∞ & 4 & a & b & a & a & b \\ 4 & \{a, b, c, d, f\} & f & 3 & 4 & 4 & ∞ & 4 & a & b & a & a & b \\ 5 & \{a, b, c, d, f, e\} & e & 3 & 4 & 4 & ∞ & 4 & a & b & a & a & b \end{matrix}

P [c] = b なので c の直前は b、 P [b] = a なので b の直前は a であり、 c への最短経路は、 a, b, c と分かります。

各頂点への最短経路は、

\begin{matrix}目的点 & 最短距離 & 最短経路 \\ b & 3 & a, b \\ c & 4 & a, b, c \\ d & 4 & a, d \\ e & ∞ & なし \\ f & 4 & a, b, f \end{matrix}

となります。

(b) アルゴリズム Floyd を用いて、すべての頂点間の最短距離を求めよ。また、最短経路を再現するための行列 P も作れ。

アルゴリズム Floyd を用いて、 A_{k}[i, j] を計算します。また、「最短経路で途中にある頂点」の行列 P [i, j] も計算します。最初はすべての i, j に対して

P_{0}[i, j] = 0 に初期化します。そして、それまでに見つかっていた経路よりも短い、 k を通る経路を見つけたときに、 P_{k}[i, j] = k に更新します。

A_{a} a b  c  d e  f  P_{a} a b c d e f
a 0 3  ∞  4 ∞  5  a 0 0 0 0 0 0
b ∞ 0  1  ∞ ∞  1  b 0 0 0 0 0 0
c ∞ ∞  0  2 ∞ ∞  c 0 0 0 0 0 0
d ∞ 3  ∞  0 ∞ ∞  d 0 0 0 0 0 0
e ∞ ∞ ∞  3 0  2  e 0 0 0 0 0 0
f ∞ ∞ ∞  2 ∞  0  f 0 0 0 0 0 0
A_{b}  P_{b}
0 3 3 + 1 4 ∞ 3 + 1  0 0 b 0 0 b
∞ 0  1  ∞ ∞  1  0 0 0 0 0 0
∞ ∞  0  2 ∞ ∞  0 0 0 0 0 0
∞ 3 3 + 1 0 ∞ 3 + 1  0 0 b 0 0 b
∞ ∞ ∞  3 0  2  0 0 0 0 0 0
∞ ∞ ∞  2 ∞  0  0 0 0 0 0 0

: : :

A_{f}  P_{f}
0 3  4  4 ∞  4  0 0 b 0 0 b
∞ 0  1  3 ∞  1  0 0 0 c 0 0
∞ 5  0  2 ∞  6  0 d 0 0 0 d
∞ 3  4  0 ∞  4  0 0 b 0 0 b
∞ 6  7  3 0  2  0 d d 0 0 0
∞ 5  6  2 ∞  0  0 d d 0 0 0

P [c, f] = d なので c から f への最短経路は d を通ることが分かります。また、 P [c, d] = 0 なので c から d への最短経路は c, d であること、 d から f への最短経路は、 P [d, f] = b なので b を通り、 P [d, b] = 0, P [b, f] = 0 なので d, b, f であることが分かります。よって、 c から f への最短経路は、 c, d, b, f です。

k = f のときの a の行、すなわち A_{k}[a, j], P_{k}[a, j] は、それぞれ、前問 (a) の D[j], P [j] に相当します。

(a) の Dijkstra では V − S の中で D[w] が最小であるような頂点 w、 (b) の Floyd では順番の頂点 k、をそれぞれ選びますが、偶然、いずれも最初（a の次）に b が選ばれています。このため、 k < f のときも、 A_{k}[a, j], P [a, j] は、それぞれ、 (a) の D[j], P [j] と等しくなっています。

6.6 弧のコストが負であってもよいものとすると、プログラム Dijkstra が正しく働かないことを示せ。

反例として、プログラム Dijkstra が正しく働かないような、コストが負の弧をもつ有向グラフを示します。

a b c
a  2 1
b  −2

c

a から c への正しい最短経路は、明らかに距離 0 の a, b, c ですが、 Dijkstra を適用すると、

\begin{matrix}繰返し & S & w & D[b] & D[c] & P [b] & P [c] \\ 初期状態 & \{a\} & — & 2 & 1 & a & a \\ 1 & \{a, c\} & c & 2 & 1 & a & a \\ 2 & \{a, c, b\} & b & 2 & 1 & a & a \end{matrix}

距離 1 の経路 a, c となってしまいます。

6.7 弧のコストに負のものがあっても、負のコストをもつ閉路がなければプログラム Floyd が正しく動

くことを示せ。

負のコストをもつ閉路があるとプログラム Floyd が正しく動かないことを示します。 −r のコストをもち、頂点 v を通る閉路があるとします。 v から出発して、この閉路を 1, 2, .. 周すると、コストは −r, −2r, .. となり、 −∞ に発散します。つまり、この閉路の中の頂点を通る経路については最短距離が存在しません。

負のコストをもつ閉路がなければプログラム Floyd が正しく動くことを示します。 Floyd の各 A_{k}[i, j] は、頂点 i から出発し、 0 番目から k 番目までの頂点を最大 1 度通って頂点 j へ到達する経路の距離を表しています。

このとき、非負のコストをもつ閉路は無視できます。なぜなら、非負のコストをもつ閉路は 1 周が最短距離であり、周回してもコストが低くなることはないからです。 r の非負コストをもつ閉路を何周しても、 r, 2r, .. と、コストが減ることはなく、 min(r, 2r, ..) = r なので、最大 1 周しか考えない Floyd で最短距離を求めることができます。

しかし、負のコストをもつ閉路は周回するたびにコストが低くなり、最大 1 周しか考えない Floyd では最短距離を求めることができません。実際の最短距離は −∞ に発散してしまいます。

比較

Dijkstra と Floyd のループ不変条件 (invariant) に関する比較を行います。

頂点の集合 V と弧のコスト行列 C は共通の不変式です。特定の有向グラフに対する最短経路問題において、頂点と弧の性質は不変だからです。

Dijkstra では、各繰返しにおいて特別な経路をもつ頂点 v ∈ S への最短距離は D[v] であるという不変条件があります。つまり、特別な経路をもつ頂点 v への最短距離は、 v を S_{k} に入れるまでの間に計算し終わり、出発点からの距離が v よりも遠い頂点 w を通過する経路は遠回りであるとされ、無視されています。これは弧のコストが非負であるという条件を前提にしています。 C[w, v] < D[v]−D[w] であるような負のコストをもつ弧があると、 D[v] よりも短い D[w]+C[w, v] という経路が存在しますが、 Dijkstra ではこの可能性を考えていません。

Floyd の、各繰返しにおける A_{k}[i, j] の変化と不変条件について考察します。

まず、 A_{0}[i, j] = C[i, j] に初期化されます。これは明らかに、 i, j 以外の頂点を通らない経路を表しています。 A_{0}[i, i] = 0 なのは、コスト 0 の弧を通った距離です。 A_{0}[i, j] = ∞ ならば、 i, j 以外の頂点を通らずに目的点に到達する経路がないことを表します。

繰返しに入ると、 A_{1}[i, j] = min(A_{0}[i, j], A_{0}[i, 1] + A_{0}[1, j]) に更新されます。これは、 i, j, 1 以外の頂点を通らない最短経路を表しています。 i, j, 1 だけを通る経路は、 i, j と i, 1, j の 2 通りですが、

\begin{matrix}いずれも存在しない場合 & A_{1}[i, j] = min(∞, ∞) = ∞ & で正しい。 \\ 一方が存在しない場合 & A_{1}[i, j] = min(r, ∞) = r & で正しい。 \\ 両方とも存在する場合 & A_{1}[i, j] = min(A_{0}[i, j], A_{0}[i, 1] + A_{0}[1, j]) & で正しい。 \end{matrix}

と、どの場合でも最短距離を求めることができます。

数学的帰納法によって、 A_{k}[i, j] が i, j, 1..k 以外の頂点を通らない最短経路を表すことを示します。

A_{1}[i, j] については、すでに示しました。

A_{k}[i, j] が i, j, 1..k 以外の頂点を通らない最短経路であるとき、 A_{k+1}[i, j] が i, j, 1..k+1 以外の頂点を通らない最短経路であることを示します。 A_{k+1}[i, j] = min(A_{k}[i, j], A_{k}[i, k + 1] + A_{k}[k + 1, j]) に更新されますが、 A_{k}[i, k+1]+A_{k}[k+1, j] は、 k+1 を通り i, j, 1..k+1 以外の頂点を通らない最短経路を表しています。なぜなら、一般に min{x ∈ X} + min{y ∈ Y } = min{x + y | x ∈ X, y ∈ Y } だからです。よって、 min(A_{k}[i, j], A_{k}[i, k + 1] + A_{k}[k + 1, j]) は、 i, j, 1..k + 1 以外の頂点を通らない最短経路を表します。

Floyd の不変条件は、弧のコストが非負であるという条件を含んでいません。よって、負のコストをもつ弧があっても、負のコストをもつ閉路がなければ Floyd を適用することができます。