算法导论23.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 6.6k 阅读时长 ≈ 6 分钟

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'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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''。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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,v_j}=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\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'''给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
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来保证路径能够被正确遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 这个函数用来打印除了起点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)\)。

1
2
3
4
5
6
7
8
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})\)。