课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 3。

各层的情况

A
B D
C E
F

Q的状态变化：

[A]
[B, D]
[D, C, E]
[C, E]
[E, F]
[F]
[]

2. Dijkstra’s Algorithm Fails on Negative Edges

情形1：

   A
B     C

A <-> B : 3.5
A <-> C : 3
B <-> C : -1

起点为$A$，则结果为

  • dist(A) = 0
  • dist(B) = 3.5
  • dist(C) = 3

但是正确结果为

  • dist(A) = 0
  • dist(B) = 2（$A\to B \to C$）
  • dist(C) = 2.5（$A\to C \to B$）

情形2：

D    C
A    B

A <-> B : 100
A <-> D : 100
B <-> C : -1
D <-> C : -1

起点为$A$，则结果为

  • dist(A) = 0
  • dist(B) = 100
  • dist(C) = 99
  • dist(D) = 100

显然该情形结果正确。

3. Fixing Dijsktra’s Algorithm with Negative Weights

   A
B     C

A <-> B : 3.5
A <-> C : 3
B <-> C : -1

所有边都加上100变成：

   A
B     C

A <-> B : 103.5
A <-> C : 103
B <-> C : 99

起点为$A$，则最短路径为：

  • $A\to B$
  • $A\to C$

结果为

  • dist(A) = 0
  • dist(B) = 2.5
  • dist(C) = 3

但是正确结果为

  • dist(A) = 0
  • dist(B) = 2（$A\to B \to C$）
  • dist(C) = 2.5（$A\to C \to B$）

4. Bellman-Ford Practice

(a)
0 1 3 4 5 6 7
$A$ 0 0 0 0 0 0 0
$B$ $\infty$ 1 1 1 1 1 1
$C$ $\infty$ $\infty$ 9 9 9 0 0
$D$ $\infty$ 8 8 8 -1 -1 -1
$E$ $\infty$ 0 0 0 -1 -1 -1
$F$ $\infty$ $\infty$ $\infty$ $\infty$ 1 1 1
$G$ $\infty$ $\infty$ -4 -4 -4 -4 -4
$H$ $\infty$ $\infty$ $\infty$ -3 -3 -3 -3
$I$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$
(b)

$A\to B\to G \to H \to A$为负环。

检测方法为在进行$|V|-1$轮循环后再运行一轮循环，如果某个节点dist减少了，则说明存在负环。

该方法成立是因为，如果存在最短路路径，那么路径上的节点数量必然小于等于$|V|$。

(c)

当且仅当从源点到其他顶点的最短路径唯一。

5. Midterm Prep: Graph Short Answer

(a)

运行DFS。

(b)

时间复杂度为$O(|V|+|E|)$。

(c)

700。

(d)

不正确。

(e)
A  B
C  D
  • $A\to B$
  • $A\to C$
  • $C\to D$
  • $D\to B$

拓扑排序：

  • $A,C, D, B$

从源点$A$开始运行，那么结果为

  • dist(A) = 0
  • dist(B) = 1
  • dist(C) = 1
  • dist(D) = 2

因此$B$在$D$前面，这就和拓扑排序不符。

(f)

时间复杂度为

6. Midterm Prep: Dijkstra Tiebreaking

增加变量cnt[n]即可，源点的值初始化为$0$，其余节点的值初始化为$\infty$，然后增加如下判断：

  • if dist(v) = dist(u) + l(u, v):
    • if cnt[v] < cnt[u] + 1:
      • prev(v) = u
      • cnt[v] = cnt[u] + 1

7. Midterm Prep: Divide-and-Conquer

记输入为$n$时的输出行数为$T(n)$，那么

这里$n=2^k, k=\log_2 n,k\in \mathbb Z^{+}$，那么

记

那么

两边同除$3^k$可得

注意

将$k=\log_2 n$代入可得