跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2009年8月実施 筆記試験 第1問

标签：

Author​

itsuitsuki

Description​

Given a directed graph G=(V,E)G = (V, E), we would like to find all-pairs shortest path lengths which are the all shortest path lengths between every pair of vertices, where the size of the set V,∣V∣=nV, |V| = n. Let euve_{uv} denote a directed edge from a vertex uu to a vertex vv, and δuv\delta_{uv} denote the length of the edge euve_{uv}. The graph GG may have a negative length edge but does not have any negative length cycle. The length of the edge from the vertex uu to the same vertex u,δuu=0u, \delta_{uu} = 0, and when there exists no edge from the vertex uu to the vertex vv, δuv=∞\delta_{uv} = \infty.

Algorithm 1 on the next page outputs the single-source shortest path lengths. Let s∈Vs \in V be a single source vertex, the shortest path length from the vertex ss to a vertex v∈Vv \in V is stored in d(v)d(v). Algorithm 2 outputs the all-pairs shortest path lengths table DD, where the length of the shortest path from a vertex uu to a vertex vv is stored in D(u,v)D(u, v). Each algorithm uses d(k)d^{(k)} and D(k)(k=0,1,… )D^{(k)} (k = 0, 1, \dots) to store interim results, respectively. Answer the following questions.

(1) Apply Algorithm 1 to the graph G1=(V1,E1)G_1 = (V_1, E_1) in Figure 1 to obtain the shortest path length from a single-source vertex v0v_0. Table 1 shows d(0)d^{(0)} in Algorithm 1. Show the single-source path length d(1),d(2),d(3)d^{(1)}, d^{(2)}, d^{(3)}, and d(4)d^{(4)} from the single-source vertex v0v_0.

(2) Apply Algorithm 2 to the graph G1=(V1,E1)G_1 = (V_1, E_1) in Figure 1 to obtain the all-pairs shortest path lengths. Table 2 shows D(0)D^{(0)} in Algorithm 2. Show the selected vertex w∈V1w \in V_1 in the Main Loop and the corresponding table D(1),D(2),D(3),D(4)D^{(1)}, D^{(2)}, D^{(3)}, D^{(4)}, and D(5)D^{(5)}.

(3) To obtain all-pairs shortest path lengths, consider Algorithm 1-ALL which applies Algorithm 1 for all vertices in VV as a single-source vertex. Compare Algorithm 1-ALL and Algorithm 2.

Table 1: d(0)d^{(0)} in Algorithm 1

destination
v0v_00
v1v_1∞\infty
v2v_2∞\infty
v3v_3∞\infty
v4v_4∞\infty

Table 2: D(0)D^{(0)} in Algorithm 2

source\destinationv0v_0v1v_1v2v_2v3v_3v4v_4
v0v_001∞\infty59
v1v_1∞\infty013∞\infty
v2v_2∞\infty∞\infty0-1∞\infty
v3v_3∞\infty1∞\infty01
v4v_41∞\infty∞\infty∞\infty0

Algorithm 1

for all v ∈ V do
    d^(0)(v) = ∞
end for
d^(0)(s) = 0

/* Main Loop */
for k = 1 .. n − 1 do
    for all e_uv ∈ E do
        d^(k)(v) = min(d^(k−1)(v), d^(k−1)(u) + δ_uv)
    end for
end for

Algorithm 2

k = 0
for all u ∈ V do
    for all v ∈ V do
        D^(k)(u,v) = δ_uv
    end for
end for

/* Main Loop */
for all w ∈ V do
    for all u ∈ V do
        for all v ∈ V do
            D^(k+1)(u,v) = min(D^(k)(u,v), D^(k)(u,w) + D^(k)(w,v))
        end for
    end for
    k = k + 1
end for

题目描述​

给定含 n=∣V∣n=|V| 个顶点的有向图 G=(V,E)G=(V,E)，求任意两顶点之间的最短路径长度。用 euve_{uv} 表示从 uu 到 vv 的有向边，δuv\delta_{uv} 表示其长度。图中允许负权边，但不存在负权环；约定 δuu=0\delta_{uu}=0，若 uu 到 vv 无边，则 δuv=∞\delta_{uv}=\infty。

原文所给算法 1 求单源最短路：源点为 s∈Vs\in V，d(v)d(v) 存储 ss 到 vv 的最短距离，并用 d(k)d^{(k)} 存储中间结果。算法 2 求全源最短路矩阵 DD，其中 D(u,v)D(u,v) 存储 uu 到 vv 的最短距离，并用 D(k)D^{(k)} 存储中间结果。

  1. 对图 1 的 G1=(V1,E1)G_1=(V_1,E_1)，以 v0v_0 为源点执行算法 1。初值表为

    终点d(0)d^{(0)}
    v0v_000
    v1v_1∞\infty
    v2v_2∞\infty
    v3v_3∞\infty
    v4v_4∞\infty

    写出 d(1),d(2),d(3),d(4)d^{(1)},d^{(2)},d^{(3)},d^{(4)}。

  2. 对同一图执行算法 2。初始矩阵为

    源点 \ 终点v0v_0v1v_1v2v_2v3v_3v4v_4
    v0v_00011∞\infty5599
    v1v_1∞\infty001133∞\infty
    v2v_2∞\infty∞\infty00−1-1∞\infty
    v3v_3∞\infty11∞\infty0011
    v4v_411∞\infty∞\infty∞\infty00

    写出主循环各轮选中的 w∈V1w\in V_1，以及相应的 D(1),D(2),D(3),D(4),D(5)D^{(1)},D^{(2)},D^{(3)},D^{(4)},D^{(5)}。

  3. 定义算法 1-ALL：把 VV 中每个顶点依次作为源点运行算法 1，以得到全源最短路。比较算法 1-ALL 与算法 2。

Algorithm 1

for all v ∈ V do
    d^(0)(v) = ∞
end for
d^(0)(s) = 0

/* Main Loop */
for k = 1 .. n − 1 do
    for all e_uv ∈ E do
        d^(k)(v) = min(d^(k−1)(v), d^(k−1)(u) + δ_uv)
    end for
end for

Algorithm 2

k = 0
for all u ∈ V do
    for all v ∈ V do
        D^(k)(u,v) = δ_uv
    end for
end for

/* Main Loop */
for all w ∈ V do
    for all u ∈ V do
        for all v ∈ V do
            D^(k+1)(u,v) = min(D^(k)(u,v), D^(k)(u,w) + D^(k)(w,v))
        end for
    end for
    k = k + 1
end for

Kai​

(1)​

原巻の Algorithm 1 は，各辺について d(k)(v)d^{(k)}(v) を前ラウンドの値から代入する形で記されている。このままでは，同じ頂点への候補を上書きしてしまう。以下では各ラウンドを d(k)←d(k−1)d^{(k)}\gets d^{(k-1)} で初期化し，各辺について

d(k)(v)←min⁡{d(k)(v),d(k−1)(u)+δuv}d^{(k)}(v)\gets\min\{d^{(k)}(v),d^{(k-1)}(u)+\delta_{uv}\}

と候補を累積する Bellman–Ford 法として計算する。d(k)(v)d^{(k)}(v) は高々 kk 本の辺を使って到達する最短距離である。

kkv0v_0v1v_1v2v_2v3v_3v4v_4
00∞\infty∞\infty∞\infty∞\infty
101∞\infty59
201246
301215
401212

例えば v3v_3 への距離は v0→v1→v2→v3v_0\to v_1\to v_2\to v_3 により 1+1−1=11+1-1=1、v4v_4 へはさらに長さ1の辺を使って2となる。負閉路がないため最短路には単純路を選べ、必要な辺数は高々 n−1=4n-1=4 本である。

(2)​

w=v0,v1,v2,v3,v4w=v_0,v_1,v_2,v_3,v_4 の順で選ぶ。各行・列は v0,…,v4v_0,\ldots,v_4 の順である。

D(1)=(01∞59∞013∞∞∞0−1∞∞1∞0112∞60),(w=v0)\begin{gathered} D^{(1)}=\begin{pmatrix} 0&1&\infty&5&9\\ \infty&0&1&3&\infty\\ \infty&\infty&0&-1&\infty\\ \infty&1&\infty&0&1\\ 1&2&\infty&6&0 \end{pmatrix},\\ (w=v_0) \end{gathered}
D(2)=(01249∞013∞∞∞0−1∞∞120112350),(w=v1)\begin{gathered} D^{(2)}=\begin{pmatrix} 0&1&2&4&9\\ \infty&0&1&3&\infty\\ \infty&\infty&0&-1&\infty\\ \infty&1&2&0&1\\ 1&2&3&5&0 \end{pmatrix},\\ (w=v_1) \end{gathered}
D(3)=(01219∞010∞∞∞0−1∞∞120112320),(w=v2)\begin{gathered} D^{(3)}=\begin{pmatrix} 0&1&2&1&9\\ \infty&0&1&0&\infty\\ \infty&\infty&0&-1&\infty\\ \infty&1&2&0&1\\ 1&2&3&2&0 \end{pmatrix},\\ (w=v_2) \end{gathered}
D(4)=(01212∞0101∞00−10∞120112320),(w=v3)\begin{gathered} D^{(4)}=\begin{pmatrix} 0&1&2&1&2\\ \infty&0&1&0&1\\ \infty&0&0&-1&0\\ \infty&1&2&0&1\\ 1&2&3&2&0 \end{pmatrix},\\ (w=v_3) \end{gathered}
D(5)=(0121220101100−102120112320),(w=v4)\begin{gathered} \boxed{D^{(5)}=\begin{pmatrix} 0&1&2&1&2\\ 2&0&1&0&1\\ 1&0&0&-1&0\\ 2&1&2&0&1\\ 1&2&3&2&0 \end{pmatrix}},\\ (w=v_4) \end{gathered}

各段では、新しく許された中継点 ww を通らない経路と、u→w→vu\to w\to v と分けられる経路の最小値を比較する。全頂点を許した D(5)D^{(5)} が全点対最短距離である。

(3)​

Algorithm 1は修正済みBellman–Ford法、Algorithm 2はFloyd–Warshall法として比較する。どちらも負辺を扱えるが、ここでは負閉路がないことを使っている。

Algorithm 1は1始点につき n−1n-1 ラウンドで全 ∣E∣|E| 辺を調べる。各ラウンドの長さ nn の初期化も数えると O(n(n+∣E∣))O(n(n+|E|))、全始点なら O(n2(n+∣E∣))O(n^2(n+|E|)) である。通常の ∣E∣≥n|E|\ge n の範囲では、それぞれ O(n∣E∣)O(n|E|)、O(n2∣E∣)O(n^2|E|) と書ける。Algorithm 2は中継点と始終点の三重ループにより O(n3)O(n^3)。

従って ∣E∣=Θ(n2)|E|=\Theta(n^2) の密なグラフでは、全始点Bellman–Fordの O(n4)O(n^4) に対してFloyd–Warshallが O(n3)O(n^3) で有利である。∣E∣=Θ(n)|E|=\Theta(n) の疎なグラフでは両者とも O(n3)O(n^3) だが、前者は辺リストを直接利用できる。作業領域はBellman–Fordが2本の距離ベクトルで O(n)O(n)、Floyd–Warshallが行列を再利用して O(n2)O(n^2)。全点対の結果自体を保存するなら、いずれも O(n2)O(n^2) の出力領域が必要となる。

Reference​

本页目录