京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-2

标签：

• Kyoto-University
• Shortest-Path-Problem

Author

Isidore, 祭音Myyura

Description

$G = (V, E)$ を有向グラフとする。 ここで、$V$ は $G$ の頂点集合、$E$ は $G$ の辺集合である。 頂点 $u$ から頂点 $v$ への有向辺は順序対 $(u, v) \in E$ で表され、距離 $l(u,v)>0$ を持つ。 頂点は $1$ から $N$ で番号付けられており、$V = \{1, 2, \ldots, N\}$ である。 有向グラフの例を図１に示す。 各辺に付された数値はその辺の距離を表す。

頂点 $v_1$ から頂点 $v_m$ へと有向辺を辿って到達できるとき、この経路 $p$ を $(v_1, v_2, \ldots, v_m)$ で表す。 $v_1, v_m$ を除く $p$ の頂点を中間頂点と呼ぶ。 経路 $p$ の距離は $l(p)=\sum_{i=1}^{m-1} l(v_i,v_{i+1})$ で与えられる。 頂点 $u$ から頂点 $v$ への最短経路は、頂点 $u$ から頂点 $v$ への全ての経路のうち距離が最小のものである。

(1) 図１のグラフにおける頂点４から頂点３への最短経路とその距離を求めよ。

(2) 経路 $p=(v_1, \ldots, v_i, \ldots, v_j, \ldots, v_m)$ は、$v_i = v_j \ (1 \leq i < j \leq m)$ のとき、閉路を含むという。 任意の最短経路が閉路を含まないことを証明せよ。

$G$ の全ての頂点対に対して最短経路の距離を求める問題を考える。 具体的には、頂点番号を利用した動的計画法に基づくアルゴリズムを作る。 全ての中間頂点が $\{1, 2, \ldots, k\}$ に含まるという制約下での頂点 $i$ から頂点 $j$ への最短経路の距離を $\delta(i,j,k)$ とする ($0 \leq k \leq N$)。 条件を満たす経路が存在しないとき、$\delta(i,j,k)=\infty$ とする。 また $\delta(i,i,k)=0$ とする。 $k=0$ のときは、中間頂点は存在しないとする。 $\delta(i,j,k)$ を使うと、元の問題は全ての $i,j$ について $\delta(i,j,N)$ を求めることとみなせる。

(3) $1 \leq k \leq N$ のとき $\delta(i,j,k) = \min (\delta(i,j,k-1), \delta(i,k,k-1)+\delta(k,j,k-1))$ が成り立つことを示せ。

(4) $d^{(k)}$ はサイズ $N \times N$ の２次元配列であり、その要素の値は $d^{(k)}[i][j] = \delta(i,j,k)$ であるとする。 ただし、配列は１で始まるインデックス方式とする。 図１のグラフに対して、$d^{(0)}, \ldots, d^{(4)}$ をこの順番で求めることで、全ての頂点対に対して最短経路の距離を求めよ。

(5) (4) はこのアルゴリズムが $N+1$ 個の２次元配列を必要とすることを示唆するが、実際には１個の２次元配列を用意すれば済むことを示せ。

(6) (5) の結果を用いると次のアルゴリズムを導ける。下の空欄 (a) および (b) を埋めよ。

Kai

(1)

• The shortest path is $(v_4, v_2, v_1, v_3)$.
• The distance is $5$.

(2)

Assume that there is a cycle start and end at $v_i$ in a shortest path $p=(v_1, ..., v_i, ..., v_i, ...v_m)$ from $v_1$ to $v_m$. Then,

$$l(p) = l(v_1, \ldots, v_i) + l(v_i, \ldots, v_i) + l(v_i, \ldots, v_m)$$

Since $l(u,v) > 0$ for any edge $(u,v) \in E$, we have $l(v_i, \ldots, v_i) > 0$. Thus, the path $p' = (v_1...v_i...v_m)$ of weight

$$l(p') = l(v_1, \ldots, v_i) + l(v_i, \ldots, v_m)$$

is shorter than $p$, which leads to a contradiction with the assumption that $p$ is a shortest path. Therefore, no shortest path contains a cycle.

(3)

Let $p_{ijk}$ be a shortest path from vertex $i$ to vertex $j$ such that all intermediate are contained in $\{1, \ldots, k\}$. By (2) we know that a shortest path does not contain the same vertex twice, hence there are two possibilities to construct $p_{ijk}$.

1. vertex $k$ is not a vertex on the path, then we have $l(p_{ijk}) = \delta (i, j, k-1)$.
2. vertex $k$ is a vertex on the path, then the path consists of a subpath from $i$ to $k$ and a subpath from $k$ to $j$. Each subpath can only contain intermediate vertices in $\{1, \ldots , k-1\}$, and also shortest paths from $i$ to $k$ and $k$ to $j$ respectively (otherwise a shorter path from $i$ to $j$ can be constructed), namely they have lengths $\delta(i, k, k-1)$ and $\delta(k, j, k-1)$, respectively. Hence $l(p_{ijk}) = \delta(i, k, k-1) + \delta(k, j, k-1)$.

Combining the two cases we have

$$\delta(i,j,k) = \min (\delta(i,j,k-1), \delta(i, k, k-1) + \delta(k, j, k-1))$$

(4)

$$d^{(0)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & \infty & \infty \\ \infty & \infty & 0 & 2 \\ 4 & 1 & \infty & 0 \\ \end{bmatrix}$$ $$d^{(1)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & 4 & \infty \\ \infty & \infty & 0 & 2 \\ 4 & 1 & 6 & 0 \\ \end{bmatrix}$$ $$d^{(2)}= \begin{bmatrix} 0 & 1 & 2 & \infty \\ 2 & 0 & 4 & \infty \\ \infty & \infty & 0 & 2 \\ 3 & 1 & 5 & 0 \\ \end{bmatrix}$$ $$d^{(3)}= \begin{bmatrix} 0 & 1 & 2 & 4 \\ 2 & 0 & 4 & 6 \\ \infty & \infty & 0 & 2 \\ 3 & 1 & 5 & 0 \\ \end{bmatrix}$$ $$d^{(4)}= \begin{bmatrix} 0 & 1 & 2 & 4 \\ 2 & 0 & 4 & 6 \\ 5 & 3 & 0 & 2 \\ 3 & 1 & 5 & 0 \\ \end{bmatrix}$$

(5)

By the formula proposed in (3), we have

$$\begin{align} \delta(i, k, k) &= \min (\delta(i,k,k-1), \delta(i, k, k-1)+\delta(k, k, k-1))\\ &=\delta(i, k , k-1) \end{align}$$

which means the elements in the $k$-th row or the $k$-th column stays the same when deriving $d^{(k)}$ from $d^{(k-1)}$.

Hence we can derive each new value in-place. Thus, only one array is required.

(6)

• (a) $d[i][j] > d[i][k] + d[k][j]$
• (b) $d[i][j] \leftarrow d[i][k] + d[k][j]$