算法导论 23.1 Exercises 答案

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

23.1-1

运行 SLOW-APSP 的每步迭代结果：

(0∞∞∞−1∞10∞2∞∞∞20∞∞−8−4∞∞03∞∞7∞∞0∞∞510∞∞0)m=2→(06∞∞−1∞−20∞20∞3−304∞−8−410∞0−5∞87∞90∞65107∞0)m=3→(06∞8−1∞−20∞2−3∞−2−30−12−8−42∞0−5∞57∞90∞3510750)m=4→(06∞8−1∞−20∞2−3∞−2−30−12−8−42∞0−5∞57∞90∞3510750)m=5→(06∞8−1∞−20∞2−3∞−5−30−1−6−8−42∞0−5∞57∞90∞3510720)

运行 FAST-APSP 的每步迭代结果：

(0∞∞∞−1∞10∞2∞∞∞20∞∞−8−4∞∞03∞∞7∞∞0∞∞510∞∞0)m=2→(06∞∞−1∞−20∞20∞3−304∞−8−410∞0−5∞87∞90∞65107∞0)m=4→(06∞8−1∞−20∞2−3∞−2−30−12−8−42∞0−5∞57∞90∞3510750)m=8→(06∞8−1∞−20∞2−3∞−5−30−1−6−8−42∞0−5∞57∞90∞3510720)

23.1-2

因为这采用了如下事实：从节点 i 回到自身的最短路径是一条空路径（没有负环的情况下），因此 wii=0。

如果不使用 wii=0，那么 lij(r) 求的是从 i 到 j 恰好包含 r 条边的最短路径。那么到最后，还需要求解 δ(i,j)=mink=1n{lij(k)}，这将增加多余的代码量。

23.1-3

由于任何矩阵 A 和矩阵 L(0)“相乘” 所得到的矩阵为 A，因此 L(0) 相当于是普通矩阵乘法中的单位矩阵。

23.1-4

不是一般性，考虑 n 阶级矩阵 Wa,Wb,Wc，那么我们相当于证明 (Wa⋅Wb)⋅Wc=Wa⋅(Wb⋅Wc)。

考虑 (Wa⋅Wb)⋅Wc 的第 x 行第 y 列的值 wxy 以及 Wa⋅(Wb⋅Wc) 的第 x 行第 y 列的值 wxy′，那么有

wxy=minj=1n{mini=1n{wxia,wijb},wjyc}=minj=1nmini=1n{wxia,wijb,wjyc}=mini=1n{wxia,minj=1n{wijb,wjyc}}=wxy′

因此，这个矩阵运算的结合律成立，也就是有 (Wa⋅Wb)⋅Wc=Wa⋅(Wb⋅Wc)。

23.1-5

假设现在是求以原点为 s 的单源最短路。令 v0 表示一个长度为 n 的行向量，其中 vs0=0，并且对于 ∀i≠s,vi0=∞。

那么，对于向量 vi，有 vi=vi−1W。那么我们只需要花费 O(n3) 的时间就可以计算出 vn−1=v0⋅Wn−1。最终，向量 vn−1 就代表从原点 s 到各点的最短距离值。

在计算 vi=vi−1W 的过程就相当于是 Bellman-Ford 算法中的每一步迭代，W 中的每一个元素 wi,j 进行了一次乘法运算后，相当于在 Bellman-Ford 算法中边 (i,j) 进行了一次松弛。

23.1-6

对子程序 EXTEND-SHORTEST-PATHS 和 SLOW-APSP 改写后的结果如下。事实上，这种更新方式是正确的，因为这相当于是 Bellman-Ford 算法进行松弛的过程：如果 v.d>u.d+w(u,v)，那么将 u.d+w(u,v) 原地赋值给 c.d。只是在这里可以视为相当于对每个节点执行了总共 n 次的 Bellman-Ford 算法，这里的 l⋅u 就相当于 Bellman-Ford 算法的 u.d。因此，从前往后进行了 n−1 次松弛，这个改动是没错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
EXTEND-SHORTEST-PATHS'(L, W, n)
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        l_{ij} = min{l_{ij}, l_{ik} + w_{kj}}


SLOW-APSP'(W, L(0), n)
  let L=(l_{ij}) and M = (m_{ij}) be new n × n matrices
  L = L(0)
  for r = 1 to n - 1
    EXTEND-SHORTEST-PATHS'(L, W, n)
  return L

然而，FAST-APSP 不能省略 M，因为计算 M=L2 时需要保证 L 和 L（左边的和右边的 L）都是正确的。

23.1-7

直接暴力枚举所有节点 i，然后以 i 为原点进行 BFS。具体做法是，对于图 Gs=(V,Es)，如果 lsv=lsu+wuv，那么 (u,v)∈Ei，那么从节点 i 开始进行 BFS，遍历所有节点最终得到的 j.π 值填入 πij 即可。由于使用的是邻接矩阵，因此进行一次 BFS 的时间复杂度为 O(n2)，总共需要花费 O(n3) 的时间才能构建出前驱矩阵 Π。整个过程由 CONSTRUCT-PI 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//假设子程序BFS-MAT(G, s)用于对图G进行BFS，且其原点为s。这里输入的G是以邻接矩阵来存储。
CONSTRUCT-PI(L, W, n)
  let Π be new n × n matrix
  V = {1, 2, 3, ..., n}
  for s = 1 to n
    E = ∅
    for u = 1 to n
      for v = 1 to n
        if l_{sv} == l_{su} + w_{uv}
        E = E ∪ {(u, v)}
    BFS-MAT((V, E))
    for v = 1 to n
      π_{sv} = v.π
  return Π

23.1-8

将 Π 中的每一行视为是一个独立的 Bellman-Ford 算法正在进行松弛操作，并且沿用 Π(i−1) 的值来构造出 Π(i)。需要注意的是，Π(0) 的值为全空。具体的过程如下给出，可以发现，SLOW-APSP''' 的时间复杂度同样为 Θ(n4)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
EXTEND-SHORTEST-PATHS'''(L, Π, W, n)
  let L' be new n × n matrix by ∞
  Π' = Π
  for i = 1 to n
    for j = 1 to n
      for k = 1 to n
        if l'_{ij} > l_{ik} + w_{kj}
          l'_{ij} = l_{ik} + w_{kj}
          π'_{ij} = k
  return L', Π'


SLOW-APSP'''(W, L(0), n)
  let Π be new n × n matrix by NIL
  L = L(0)
  for r = 1 to n - 1
    L, Π = EXTEND-SHORTEST-PATHS''(L, Π, W, n)
  return L, Π

23.1-9

在整个循环结束后，再进行一次迭代，从而得到 M=W2m,L=Wm,m≥n−1。如果 M 和 L 不相同，那么说明存在一条长度超过 n−1 的最短路，因此这个图有负环。

整个算法由程序 FASTER-APSP' 给出，其时间复杂度为 Θ(n3lg⁡n)，相比起 FASTER-APSP，仅仅是多运行了一次程序 EXTEND-SHORTEST-PATHS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FASTER-APSP'(W, n)
  let L and M be new n × n matrices
  L = W
  r = 1
  while r < n - 1
    M = ∞  // initialize M
    EXTEND-SHORTEST-PATHS(L, L, M, n) // compute M = L^2
    r = 2r
    L = M // ready for the next iteration
  M = ∞
  EXTEND-SHORTEST-PATHS(L, L, M, n)
  for i = 1 to n
    for j = 1 to n
      if l_{ij} != m_{ij}
        return False
  return True

23.1-10

最基本的想法很简单：只要找到最小的 m，∃i,lii(m)<0 即可。也就是说从 i 到 i 已经存在一条负数边权的路径。

其中一种最简单的做法是，从小到大枚举 m 值，计算出 L(m) 后直接判断即可。这个过程由 MINIMUM-NEG-CYCLE 给出，可以看出这个算法是基于 SLOW-APSP 的，其时间复杂度为 O(n4)。

1
2
3
4
5
6
7
8
9
10
11
12
13
MINIMUM-NEG-CYCLE(W, L(0), n)
  let L=(l_{ij}) and M = (m_{ij}) be new n × n matrices
  L = L(0)
  // 最短的负环长度可能达到n，需要注意。
  for r = 1 to n
    M = ∞
    EXTEND-SHORTEST-PATHS'(L, W, n)
    L = m
    for i = 1 to n
      if l_{ii} < 0
        return r
  // 不存在负环。
  return -1

另外一种做法则是基于 FASTER-APSP 的，使用倍增法进行实现。每次将当前矩阵 L 尝试乘上一个 L(m)，得到新矩阵 L′。如果仍未检测出负环，那么用 L′ 代替 L，并将 m 翻倍，否则将 m 进行减半。

在这种情况下，EXTEND-SHORTEST-PATHS 将只会被调用 O(lg⁡n) 次，因此整个程序的时间复杂度为 O(n3lg⁡n)。完整过程由 MINIMUM-NEG-CYCLE' 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
MINIMUM-NEG-CYCLE'(W, n)
  L = L(1) = W
  m = 1
  k = 1
  while k < n or m > 0
    M = ∞
    if k + m > n
      m = ⌊m / 2⌋
    else
      if L(m) == NIL
        L(m) = ∞
        EXTEND-SHORTEST-PATHS(L(m/2), L(m/2), L(m), n)
      EXTEND-SHORTEST-PATHS(L, L(m), M, n)
      have-neg-cycle = False
      for i = 1 to n
        if m_{ii} < 0
          have-neg-cycle = True
      if have-neg-cycle == True
        m = ⌊m / 2⌋
      else
        L = M
        k = k + m
        m = m * 2
  if k < n
    // 找到了负环。
    return k + 1
  else
    // 没有找到负环。
    return -1