京都大学 情報学研究科 知能情報学専攻 2022年8月実施 情報学基礎 F2-2
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,
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
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}\).
- vertex \(k\) is not a vertex on the path, then we have \(l(p_{ijk}) = \delta (i, j, k-1)\).
- 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
(4)
(5)
By the formula proposed in (3), we have
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]\)