算法导论22.1 Exercises 答案

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

22.1-1

第一个问题的迭代过程如下：

\(\begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&\infty&\text{NIL}\\\hline t&\infty&\text{NIL}\\\hline x&\infty&\text{NIL}\\\hline y&\infty&\text{NIL}\\\hline z&0&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&2&z\\\hline t&\infty&\text{NIL}\\\hline x&7&z\\\hline y&\infty&\text{NIL}\\\hline z&0&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&2&z\\\hline t&5&x\\\hline x&7&z\\\hline y&9&s\\\hline z&0&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&2&z\\\hline t&5&x\\\hline x&6&y\\\hline y&9&s\\\hline z&0&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&2&z\\\hline t&4&x\\\hline x&6&y\\\hline y&9&s\\\hline z&0&\text{NIL}\\\hline \end{array}\)

第二个问题的迭代过程如下：

\(\begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&0&\text{NIL}\\\hline t&\infty&\text{NIL}\\\hline x&\infty&\text{NIL}\\\hline y&\infty&\text{NIL}\\\hline z&\infty&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&0&\text{NIL}\\\hline t&6&s\\\hline x&\infty&\text{NIL}\\\hline y&7&s\\\hline z&\infty&\text{NIL}\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&0&\text{NIL}\\\hline t&6&s\\\hline x&4&y\\\hline y&7&s\\\hline z&2&t\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&0&\text{NIL}\\\hline t&2&x\\\hline x&4&y\\\hline y&7&s\\\hline z&2&t\\\hline \end{array} \longrightarrow \begin{array}{|l|l|l|}\hline v&d&\pi\\\hline s&0&\text{NIL}\\\hline t&2&s\\\hline x&4&y\\\hline y&7&s\\\hline z&-2&t\\\hline \end{array}\)

注意到第二个问题中的图有负环，算法BELLMAN-FORD将会返回FALSE。

22.1-2

充分性：根据引理22.2，执行完Bellman-ford算法后，有\(v.d=\delta(s,v)。\)由于从\(s\)到\(v\)中存在路径，那么必定存在一条最短路径，使得\(\delta(s,v)<\infty\)，因此有\(v.d<\infty\)。

必要性：由于\(v.d<\infty\)，这说明节点\(v\)被松驰过，并且节点的\(\pi\)属性记录着这条路径的上一个节点。那么我们可以递归访问路径上其前驱节点。由于其前驱子图\(G_\pi\)是一棵以\(s\)为根的树，因此我们最终可以递归访问到\(s\)节点，这说明从\(s\)到\(v\)存在一条路径。

22.1-3

如果所有边都不再被松弛，那么说明整个算法可以结束了。因此我们使用一个布尔遍历来记录第\(i\)轮迭代是否发生了松弛，如果没有发生松弛那么可以及时结束整个算法。改进后的程序为BELLMAN-FORD'：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
RELAX'(u, v, w)
  if v.d > u.d + w(u, v)
    v.d = u.d + w(u, v)
    v.π = u
    return TRUE
  return FALSE

BELLMAN-FORD'(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i = 1 to |G.V| − 1
    relax-appear = FALSE
    for each edge (u, v) ∈ G.E
      if RELAX'(u, v, w) == TRUE
        relax-appear = TRUE
    if relax-appear == FALSE
      break
  for each edge (u, v) ∈ G.E
    if v.d > u.d + w(u, v)
      return FALSE
  return TRUE

22.1-4

如果在第\(|V|\)轮迭代中，一条边\((u,v)\)仍然进行了一次松弛操作，那么说明\(v\)存在于某个负环中。这说明，从\(v\)开始可达的节点，都不存在最短路径。因此我们标记上这些节点，然后通过DFS访问这些节点所有的可达节点，并将它们标记上\(-\infty\)即可。这个算法由BELLMAN-FORD''给出，其时间复杂度仍然为\(O(V^2+VE)\)，因为标记节点所需要的开销远远低于BELLMAN-FORD算法本身的执行过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

DFS-VISIT-BELLMAN-FORD(G, u)
  if u.d != -∞
    u.d = -∞
    for each vertex v in G.Adj[u]
      DFS-VISIT(G, v)

BELLMAN-FORD''(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i = 1 to |G.V| − 1
    for each edge (u, v) ∈ G.E
      RELAX(u, v, w)
  for each edge (u, v) ∈ G.E
    if v.d > u.d + w(u, v)
      DFS-VISIT-BELLMAN-FORD(G, v)

22.1-5

如果边集\(E\)是直接按照一个列表给定的，那么就不必再在每次迭代中遍历每个节点，再访问其对应的边。直接访问这个列表中的边进行松弛操作即可，把时间复杂度从\(O(V^2+VE)\)降到\(O(VE)\)，这在图非常稀疏时是有效的，这个算法由程序BELLMAN-FORD'''给出。

1
2
3
4
5
6
7
8
9
10
11
BELLMAN-FORD'''(G, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i = 1 to |G.V| − 1
    for each edge (u, v, w) ∈ G.E
      if u.d + w < v.d
        v.d = w + u.d
        v.π = u
  for each edge (u, v, w) ∈ G.E
    if v.d > u.d + w
      return FALSE
  return TRUE

22.1-6

也就是说，\(\delta^{\ast}(v)\)是图\(G=(V,E)\)中，\(V\)中所有节点到\(v\)的最短距离。那么所有节点的\(v.d\)的初始化值为\(0\)，因为初始化时\(d=0\)意味着从其它节点到自身距离当前的最小值。整个算法由程序CAL-DELTA-STAR给出，除了初始化步骤不相同，其它步骤都一样，此外还使用了题目22.1-4中的子程序DFS-VISIT-BELLMAN-FORD用来填充\(-\infty\)。因此最终其时间复杂度为\(O(VE)\)。

1
2
3
4
5
6
7
8
9
CAL-DELTA-STAR(G, w)
  for each vertex v ∈ G.V
    v.d = 0
  for i = 1 to |G.V| − 1
    for each edge (u, v) ∈ G.E
      RELAX(u, v, w)
  for each edge (u, v) ∈ G.E
    if v.d > u.d + w(u, v)
      DFS-VISIT-BELLMAN-FORD(G, v)

另外一个看待这一道题目的角度是，构造一个超级原点\(s\)，令\(G'=\left(V\cup\{s\},E\cup\bigcup_{v\in V}(s,v)\right)\)。并且\(\forall v\in V,w(s,v)=0\)。那么我们可以对超级原点\(s\)进行Bellman-Ford算法。其结果和程序CAL-DELTA-STAR一致。因为\(s\)相当于是将\(V\)中的所有节点集合在一起，形成一个新的起点。

22.1-7

进行完\(|V|-1\)轮的松弛操作后，如果仍然发现有\(v.d > u.d + w(u, v)\)，那么说明点\(v\)必定出现在了某一个负环\(C\)中。事实上，由于负环中的每条边都进行了反复松弛，那么\(v\)的前驱节点\(v.\pi\)也会在\(C\)中。迭代访问\(v\)的\(\pi\)属性，最终可以将一个整个环\(C\)处理出来。

整个算法由过程GET-NEG-CYCLE给出，与过程BELLMAN-FORD类似，其时间复杂度为\(O(V^2+VE)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
GET-NEG-CYCLE(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i = 1 to |G.V| − 1
    for each (u, v) ∈ G.E
      RELAX(u, v, w)
  for each u ∈ G.V
    u.mark = FALSE
  for each edge (u, v) ∈ G.E
    if v.d > u.d + w(u, v)
      Let C be new array
      v.mark = TRUE
      x = v
      while x.mark == FALSE
        INSERT(C, x)
        x.mark = TRUE
        x = x.π
      INSERT(C, v)  
      return C
  return NIL