算法导论22.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 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