算法导论23.2 Exercises 答案

23.2-1

每步的迭代结果如下：

$\begin{aligned}
&\begin{pmatrix}
0&\infty&\infty&\infty&-1&\infty\
1&0&\infty&2&\infty&\infty\
\infty&2&0&\infty&\infty&-8\
-4&\infty&\infty&0&3&\infty\
\infty&7&\infty&\infty&0&\infty\
\infty&5&10&\infty&\infty&0
\end{pmatrix}
\underrightarrow{k=1}
\begin{pmatrix}
0&\infty&\infty&\infty&-1&\infty\
1&0&\infty&2&0&\infty\
\infty&2&0&\infty&\infty&-8\
-4&\infty&\infty&0&-5&\infty\
\infty&7&\infty&\infty&0&\infty\
\infty&5&10&\infty&\infty&0
\end{pmatrix}
\underrightarrow{k=2}
\begin{pmatrix}
0&\infty&\infty&\infty&-1&\infty\
1&0&\infty&2&0&\infty\
3&2&0&4&2&-8\
-4&\infty&\infty&0&-5&\infty\
8&7&\infty&9&0&\infty\
6&5&10&7&5&0
\end{pmatrix}\
\underrightarrow{k=3}
&\begin{pmatrix}
0&\infty&\infty&\infty&-1&\infty\
1&0&\infty&2&0&\infty\
3&2&0&4&2&-8\
-4&\infty&\infty&0&-5&\infty\
8&7&\infty&9&0&\infty\
6&5&10&7&5&0
\end{pmatrix}
\underrightarrow{k=4}
\begin{pmatrix}
0&\infty&\infty&\infty&-1&\infty\
-2&0&\infty&2&-3&\infty\
0&2&0&4&-1&-8\
-4&\infty&\infty&0&-5&\infty\
5&7&\infty&9&0&\infty\
3&5&10&7&2&0
\end{pmatrix}
\underrightarrow{k=5}
\begin{pmatrix}
0&6&\infty&8&-1&\infty\
-2&0&\infty&2&-3&\infty\
0&2&0&4&-1&-8\
-4&2&\infty&0&-5&\infty\
5&7&\infty&9&0&\infty\
3&5&10&7&2&0
\end{pmatrix}\
\underrightarrow{k=6}
&\begin{pmatrix}
0&6&\infty&8&-1&\infty\
-2&0&\infty&2&-3&\infty\
-5&-3&0&-1&-6&-8\
-4&2&\infty&0&-5&\infty\
5&7&\infty&9&0&\infty\
3&5&10&7&2&0
\end{pmatrix}\
\end{aligned}$

23.2-2

对于图$G=(V,E)$的邻接矩阵$W$，我们设$w{ij}=1$当且仅当边$(i,j)\in E$，此外，$\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,\forall j\in[1,m],\pi^{(k)}{i,vj}=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,vm}$被更新成$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},vj)}<0$。这和图$G$没有负环是矛盾的。因此，$G{\pi,i}$是一个有向无环图。

接下来和引理22.17的证明类似。$G{\pi,i}$从$i$到每个节点$u$之间只存在唯一一条路径。如果存在两条路径$p_1:i\rightsquigarrow u\rightsquigarrow x\rightarrow z\rightsquigarrow u,p_2:i\rightsquigarrow u\rightsquigarrow y\rightarrow z\rightsquigarrow u$，并且$x\neq 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^{k-1}{ik}+d^{k-1}{ki}<0$的更新导致了主对角线上$d^{k}_{ii}$的值小于$0$。

23.2-7

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

$\phi^{(k)}{ij}=
\left {\begin{aligned}
&k & & \text{if}\quad d^{(k-1)}{ij} > d^{(k-1)}{ik}+d^{(k-1)}{kj} \
&\phi^{(k-1)}{ij} & & \text{if}\quad d^{(k-1)}{ij} \le d^{(k-1)}{ik}+d^{(k-1)}{kj} \
\end{aligned}\right.$

那么可以将Floyd-Warshall算法进行改写以求出$\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

表$Φ$和矩阵链乘所得到的表$s$是一样的，它们表示的内容都是当前最优情况下，对对路径/乘法阶段的最优划分。然而，$\Phi$表的路径追踪比$s$表难，因为$\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)$的时间。对于$\forall (v_i,v_j)\in E^{SCC\ast}$，$\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})$。