算法导论 23.2 Exercises 答案

23.2-1

每步的迭代结果如下：

$\begin{array}{rl}& \left(\begin{array}{cccccc}0& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& -1& \mathrm{\infty }\\ 1& 0& \mathrm{\infty }& 2& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& 2& 0& \mathrm{\infty }& \mathrm{\infty }& -8\\ -4& \mathrm{\infty }& \mathrm{\infty }& 0& 3& \mathrm{\infty }\\ \mathrm{\infty }& 7& \mathrm{\infty }& \mathrm{\infty }& 0& \mathrm{\infty }\\ \mathrm{\infty }& 5& 10& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)\underrightarrow{k=1}\left(\begin{array}{cccccc}0& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& -1& \mathrm{\infty }\\ 1& 0& \mathrm{\infty }& 2& 0& \mathrm{\infty }\\ \mathrm{\infty }& 2& 0& \mathrm{\infty }& \mathrm{\infty }& -8\\ -4& \mathrm{\infty }& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ \mathrm{\infty }& 7& \mathrm{\infty }& \mathrm{\infty }& 0& \mathrm{\infty }\\ \mathrm{\infty }& 5& 10& \mathrm{\infty }& \mathrm{\infty }& 0\end{array}\right)\underrightarrow{k=2}\left(\begin{array}{cccccc}0& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& -1& \mathrm{\infty }\\ 1& 0& \mathrm{\infty }& 2& 0& \mathrm{\infty }\\ 3& 2& 0& 4& 2& -8\\ -4& \mathrm{\infty }& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 8& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 6& 5& 10& 7& 5& 0\end{array}\right)\\ \underrightarrow{k=3}& \left(\begin{array}{cccccc}0& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& -1& \mathrm{\infty }\\ 1& 0& \mathrm{\infty }& 2& 0& \mathrm{\infty }\\ 3& 2& 0& 4& 2& -8\\ -4& \mathrm{\infty }& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 8& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 6& 5& 10& 7& 5& 0\end{array}\right)\underrightarrow{k=4}\left(\begin{array}{cccccc}0& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& -1& \mathrm{\infty }\\ -2& 0& \mathrm{\infty }& 2& -3& \mathrm{\infty }\\ 0& 2& 0& 4& -1& -8\\ -4& \mathrm{\infty }& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 5& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 3& 5& 10& 7& 2& 0\end{array}\right)\underrightarrow{k=5}\left(\begin{array}{cccccc}0& 6& \mathrm{\infty }& 8& -1& \mathrm{\infty }\\ -2& 0& \mathrm{\infty }& 2& -3& \mathrm{\infty }\\ 0& 2& 0& 4& -1& -8\\ -4& 2& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 5& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 3& 5& 10& 7& 2& 0\end{array}\right)\\ \underrightarrow{k=6}& \left(\begin{array}{cccccc}0& 6& \mathrm{\infty }& 8& -1& \mathrm{\infty }\\ -2& 0& \mathrm{\infty }& 2& -3& \mathrm{\infty }\\ -5& -3& 0& -1& -6& -8\\ -4& 2& \mathrm{\infty }& 0& -5& \mathrm{\infty }\\ 5& 7& \mathrm{\infty }& 9& 0& \mathrm{\infty }\\ 3& 5& 10& 7& 2& 0\end{array}\right)\end{array}$

23.2-2

对于图 $G=(V,E)$ 的邻接矩阵 $W$，我们设 $w_{ij}=1$ 当且仅当边 $(i,j)\in E$，此外，$\mathrm{\forall }i\in V,w_{ii}=1$。接下来参照子程序 EXTEND-SHORTEST-PATHS，构造出子程序 EXTEND-PATHS'。那么剩下的是调用这个子程序即可求出传递闭包，整个过程和 23.1 节一致，由 TRANSITIVE-CLOSURE' 给出。

EXTEND-PATHS'(T(r-1), W, T(r), n)
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        t_{ij}^(r) = t_{ij}^(r) ∨ (t_{ik}^(r-1) ∧ w_{kj}^(r-1))

TRANSITIVE-CLOSURE'(W, n)
  let T and M be new n × n matrices
  T = W
  r = 1
  while r < n - 1
    M = 0
    EXTEND-PATHS''(T, T, M, n)
    r = 2r
    T = M
  return T

23.2-3

按照方程 23.7 和 23.8，修改后的算法为 FLOYD-WARSHALL''。

FLOYD-WARSHALL''(W, n)
  D^(0) = W
  let Π^(0) be a new n × n matrix
  for i = 1 to n
    for j = 1 to n
      if w_{ij} < ∞ and i != j
        π^(0)_{ij} = i
      else
        π^(0)_{ij} = NIL
  for k = 1 to n
    let D^(k) = (d^(k)_{ij}),Π^(k) = (π^(k)_{ij}) be new n × n matrices
    for i = 1 to n
      for j = 1 to n
        if d^(k-1)_{ij} > d^(k-1)_{ik} + d^(k-1)_{kj}
          d^(k)_{ij} = d^(k-1)_{ik} + d^(k-1)_{kj}
          π^(k)_{ij} = π^(k-1)_{kj}
        else
          d^(k)_{ij} = d^(k-1)_{ij}
          π^(k)_{ij} = π^(k-1)_{ij}
  return D^(n), Π^(n)

首先证明 $G_{\pi ,i}$ 是一个有向无环图。当 ${\pi }_{ij}^{(k)}$ 被更新成一个值 $l$ 时，说明 $d_{ij}^{(k)}=d_{il}^{(k-1)}+w_{lj}$。由于 $d_{ij}^{(k-1)}$ 是 $d_{ij}^{(k)}$ 的一个子问题选项，因此有 $d_{ij}^{(k)}\le d_{ij}^{(k-1)}$，从而得到 $d_{ij}^{(k)}\ge d_{il}^{(k-1)}+w_{lj}$。接下来的证明和引理 22.16 的证明类似。假设 $G_{\pi ,i}$ 构成了一个环 $v_0,v_1,\dots ,v_m$，其中 $v_0=v_m,\mathrm{\forall }j\in [1,m],{\pi }_{i,v_j}^{(k)}=v_{j-1}$ 都成立。那么在 ${\pi }_{i,v_m}$ 更新成 $v_{m-1}$ 前，都有：

$$d_{i,v_j}^{(k)}\ge d_{i,v_{j-1}}^{(k)}+w_{v_{j-1},v_j},j=1,2,\dots ,m-1$$

由于 ${\pi }_{i,v_m}$ 被更新，所以在 ${\pi }_{i,v_m}$ 被更新成 $v_{m-1}$ 前，有

$$d_{i,v_m}^{(k)}>d_{i,v_{m-1}}^{(k)}+w_{v_{m-1},v_m}$$

将这 $m$ 条不等式左右各自相加，最终得到 ${\displaystyle \sum _{j=1}^{m}w(v_{j-1},v_j)<0}$。这和图 $G$ 没有负环是矛盾的。因此，$G_{\pi ,i}$ 是一个有向无环图。

接下来和引理 22.17 的证明类似。$G_{\pi ,i}$ 从 $i$ 到每个节点 $u$ 之间只存在唯一一条路径。如果存在两条路径 $p_1:i⇝u⇝x\to z⇝u,p_2:i⇝u⇝y\to z⇝u$，并且 $x\ne y$，那么说明 ${\pi }_{iz}=x,{\pi }_{iz}=y$ 同时成立。这是不可能的，因此从 $i$ 到每个节点 $u$ 之间只存在唯一一条路径，$G_{\pi ,i}$ 是以 $i$ 为根形成的一棵树。

最终，由于算法正确地求解出了 $d_{ij}^{(n)}=\delta (i,j)$，因此对于所有顶点 $i,G_i$ 都是以 $i$ 为根的最短路径树。

23.2-4

可以知道，这个对 $d_{ij}^{(k)}$ 的更新本质上是来自 $\{d_{ik}^{(k)}+d_{kj}^{(k)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)},d_{ik}^{(k)}+d_{kj}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k)}\}$ 这 $4$ 组值中的某一个，我们将通过证明 $d_{ik}^{(k-1)}=d_{ik}^{(k)},d_{kj}^{(k-1)}=d_{kj}^{(k)}$，从而说明这个更新是正确的。

考虑先证明 $d_{ik}^{(k-1)}=d_{ik}^{(k)}$。根据 $d_{ij}^{(k)}$ 的定义：从 $i$ 到 $j$ 的路径中，中间节点只包含节点 $1,2,\dots ,k$ 的最短路径。由于 $k$ 是这条最短路径中的一个端点。$k$ 不在 $d_{ik}^{(k-1)}$ 中，如果再尝试多途经一个节点 $k$，那么来自路径 $d_{ik}^{(k)}$ 的最短路径必定不会劣于 $d_{ik}^{(k-1)}$（因为 $d_{ik}^{(k-1)}$ 是 $d_{ik}^{(k)}$ 的一个子问题）。因此有 $d_{ik}^{(k-1)}\ge d_{ik}^{(k)}$。如果 $k$ 是从 $i$ 到 $k$ 这条路径的一个中间节点，那么路径上就会形成环，因此有 $d_{ik}^{(k-1)}\le d_{ik}^{(k)}$。从而得出 $d_{ik}^{(k-1)}=d_{ik}^{(k)}$。

可以用类似的证明方式，得到 $d_{kj}^{(k-1)}=d_{kj}^{(k)}$。最终可知，这种更新方式是正确的。

23.2-5

由这个方式构造出来的矩阵是正确的。

此处仅讨论 $d_{ij}^{(k-1)}=d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$ 时的这种情况，因为如果等号不成立，情况和方程 23.8 时的一致。当第 $k$ 轮循环结束时，保证有 $d_{ij}^{(k)}=d_{i,{\pi }_{ij}}^{(k-1)}+d_{{\pi }_{ij},j}^{(k-1)}$。

本题对应的情况是 ${\pi }_{ij}^{(k)}={\pi }_{kj}^{(k-1)}$。由于 $d_{ij}^{(k-1)}=d_{ij}^{(k)}=d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$，因此 $k$ 也可以作为从 $i$ 到 $j$ 某条最短路径中的一个节点，由于 $d_{kj}^{(k-1)}$ 也是取自某条从 $k$ 到 $j$ 最短路径的长度，作为一条子路径，它的前驱 ${\pi }_{kj}^{(k-1)}$ 也适用于 ${\pi }_{ij}^{(k)}$。

23.2-6

如果其最终输出 $D^{(n)}$ 的主对角线上存在负数，那么说明 $G$ 中存在负环。因为某次 $d_{ik}^{k-1}+d_{ki}^{k-1}<0$ 的更新导致了主对角线上 $d_{ii}^k$ 的值小于 $0$。

23.2-7

由于 Floyd-Warshall 算法是从小到大插入中间节点 $k$ 来求解最短路径的，因此如果节点 $k$ 确实对从 $i$ 到 $j$ 的路径有实在的贡献，那么 ${\varphi }_{ij}^{(k)}=k$，否则有 ${\varphi }_{ij}^{(k)}={\varphi }_{ij}^{(k-1)}$，也就是沿用上一次迭代的结果。更正式地可以将 ${\mathrm{\Phi }}^{(k)}$ 写成：

${\varphi }_{ij}^{(k)}=\{\begin{array}{rlrl}& k& & \text{if}{d}_{ij}^{(k-1)}>d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\\ & {\varphi }_{ij}^{(k-1)}& & \text{if}{d}_{ij}^{(k-1)}\le d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\end{array}$

那么可以将 Floyd-Warshall 算法进行改写以求出 $\mathrm{\Phi }$，由 FLOYD-WARSHALL''' 给出：

FLOYD-WARSHALL'''(W, n)
  D^(0) = W
  for k = 1 to n
    let D^(k) = (d^(k)_{ij}),Φ^(k) = (ϕ^(k)_{ij}) be new n × n matrices
    for i = 1 to n
      for j = 1 to n
        if d^(k-1)_{ij} > d^(k-1)_{ik} + d^(k-1)_{kj}
          d^(k)_{ij} = d^(k-1)_{ik} + d^(k-1)_{kj}
          ϕ^(k)_{ij} = k
        else
          d^(k)_{ij} = d^(k-1)_{ij}
          d^(k)_{ij} = ϕ^(k-1)_{ij}
  return D^(n), Φ^(n)

修改后的 PRINT-ALL-PAIRS-SHORTEST-PATH 由程序 PRINT-ALL-PAIRS-SHORTEST-PATH' 给出，它需要调用一个子程序 AUX-PRINT-PATH 来保证路径能够被正确遍历。

// 这个函数用来打印除了起点s和终点t以外的所有点。
AUX-PRINT-PATH(Φ, W, n, s, t)
  if ϕ_{st} == NIL
    return
  x = ϕ_{st}
  AUX-PRINT-PATH(Φ, W, n, s, x)
  print x
  AUX-PRINT-PATH(Φ, W, n, x, t)

PRINT-ALL-PAIRS-SHORTEST-PATH(Φ, W, n, s, t)
  if ϕ_{st} == NIL and w_{st} == ∞
    print "no path from" i "to" j "exists"
  else if s == t
    print s
  else
    print s
    AUX-PRINT-PATH(Φ, W, n, s, t)
    print t

表 $\Phi$ 和矩阵链乘所得到的表 $s$ 是一样的，它们表示的内容都是当前最优情况下，对对路径 / 乘法阶段的最优划分。然而，$\mathrm{\Phi }$ 表的路径追踪比 $s$ 表难，因为 $\mathrm{\Phi }$ 表中的元素并不能直接获得特定的前驱或者是后继节点，只能向下一步步遍历。

23.2-8

枚举 $G=(V,E)$ 中的每一个节点 $s$ 进行 BFS 即可，被标记的节点都是能从 $s$ 到达的节点。枚举完 $V$ 中所有节点得到的结构恰好就是传递闭包。

整个算法由程序 TRANSITIVE-CLOSURE'' 给出。每进行一次 BFS 的时间复杂度为 $O(V+E)=O(E)$，因此进行 $|V|$ 次 BFS 的时间复杂度为 $O(VE)$。

TRANSITIVE-CLOSURE''(G)
  E = ∅
  for each s ∈ G.V
    BFS(s)
    for each v ∈ G.V
      if v.color == BLACK:
        E = E ∪ {(s, v)}
  return (G.V, E)

23.2-9

考虑以 $3$ 个步骤计算出有向图 $G=(V,E)$ 的传递闭包。

1. 先花费 $O(V+E)$ 的时间求出 $G$ 的强连通分量，再以 $O(V+E)$ 的时间计算出这些强连通分量的分量图 $G^{SCC}=(V^{SCC},E^{SCC})$。注意到，$|V^{SCC}|\le |V|,|E^{SCC}|\le |E|$，并且 $G^{SCC}$ 是一个有向无环图。

2. 使用题中算法所描述的算法求解 $G^{SCC}$ 的传递闭包 $G^{SCC\ast }=(V^{SCC},E^{SCC\ast })$，这将花费 $f(|V^{SCC}|,|E^{SCC}|)$ 的时间。由于 $f$ 是一个单调递增函数，因此说明只需要不超过 $f(|V|,|E|)$ 的时间即可构造出 $G^{SCC\ast }$。

3. 考虑通过 $G^{SCC\ast }$ 来构造 $G^{\ast }=(V,E^{\ast })$。假设求解分量图完成后，强连通分量 $C_i$ 表示图 $G$ 中属于这个分量的所有节点，$v_i$ 是 $C_i$ 在 $G^{SCC}$ 上对应的节点。那么首先枚举 $C_i$ 中的所有节点，并将它们成对的边添加到 $E^{\ast }$ 中，每次枚举并添加一条边只需要 $O(1)$ 的时间。对于 $\mathrm{\forall }(v_i,v_j)\in E^{SCC\ast }$，$\mathrm{\forall }u\in v_i,v\in v_j,(u,v)\in E^{\ast }$，同样的，每次枚举并添加一条边只需要 $O(1)$ 的时间。添加完所有边恰好需要 $O(V+E^{\ast })$ 的时间。

因此，这 $3$ 部分所需要花费的时间为 $f(|V|,|E|)+O(V+E)+O(V+E^{\ast })$，即可得到 $f(|V|,|E|)+O(V+E^{\ast })$。