知识焦点
先建立概念地图
- DFS
- pre-order
- post-order
- ancestor
- SCC
- 强连通分量
- 双连通分量
- 关键边
CS170 · 讨论课 4
图算法练习：DFS 先序/后序编号性质、强连通分量(SCC)算法变体正确性、双连通分量与关键边/顶点的线性时间算法。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：dis04.pdf、dis04-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 7 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
dis04.pdf、dis04-sol.pdf深度优先搜索 (DFS) 伪代码：
def dfs(G, s):
def explore_recursive(G, v):
visited(v) = true
previsit(v) # 设置 v 的先序编号
for each edge (v, u) in E:
对于下列每个命题，证明其为真，或给出反例说明其为假。注意 \(\text{pre}(v)\) 与 \(\text{post}(v)\) 分别表示顶点 \(v\) 的先序与后序编号。
(a) 若 \((u, v)\) 是无向图中的一条边，且在 DFS 过程中 \(\text{post}(v) < \text{post}(u)\)，则 \(u\) 是 DFS 树中 \(v\) 的祖先。
(b) 在有向图中，若存在一条从 \(u\) 到 \(v\) 的路径，且 \(\text{pre}(u) < \text{pre}(v)\)，则 \(u\) 是 DFS 树中 \(v\) 的祖先。
(c) 我们可以修改课堂上的 SCC 算法，使得在 \(G\) 上按 \(G\) 的递减先序运行 DFS，而非按 \(G^R\) 的递减后序运行。该修改后的算法仍然正确。
(d) 我们可以修改课堂上的 SCC 算法，使得第一次 DFS 在 \(G\) 上运行，第二次 DFS 在 \(G^R\) 上运行。该修改后的算法仍然正确。
顶点：w, u, v
DFS 先序/后序编号：\(w(\text{pre}=1,\text{post}=6)\)、\(u(\text{pre}=2,\text{post}=3)\)、\(v(\text{pre}=4,\text{post}=5)\)
有向边：w→u（树边，标记 T），w→v（树边，标记 T），u→w（回边，标记 B）
说明：存在路径 \(u\to w\to v\)，且 \(\text{pre}(u)=2 < \text{pre}(v)=4\)，但 \(u\) 不是 \(v\) 的祖先（\(u,v\) 是 \(w\) 的兄弟子节点）
来源：dis04-sol.pdf · 4
考虑 DFS 先序/后序编号的区间包含关系；对于假命题，尝试构造极小反例（2–3 个顶点）。
(a) 真。只有两种可能的情况：\(\text{pre}(u) < \text{pre}(v) < \text{post}(v) < \text{post}(u)\)，或 \(\text{pre}(v) < \text{post}(v) < \text{pre}(u) < \text{post}(u)\)。在第一种情况下，\(u\) 是 \(v\) 的祖先。在第二种情况下，\(v\) 在未访问 \(u\) 时就已出栈。然而，由于 \(u\) 与 \(v\) 之间有边，且 DFS 会访问 \(v\) 的所有邻居，因此这种情况不可能发生。
(b) 假。考虑从 \(w\) 开始 DFS 的如下情形（见图示反例）：存在路径 \(u \to w \to v\)，且 \(\text{pre}(u) = 2 < \text{pre}(v) = 4\)，但 \(u\) 不是 \(v\) 的祖先（\(u\) 与 \(v\) 是兄弟节点）。
(c) 假。考虑一个只有单条有向边的 2 顶点图，即 \(G = (V = \{v_1, v_2\}, E = \{(v_1, v_2)\})\)。若从 \(v_2\) 开始 DFS，则 \(G\) 中先序编号最大的顶点是 \(v_1\)。然而 \(v_1\) 并非汇点 SCC，因此该修改后的算法会返回错误答案。
(d) 真。\(G\) 的强连通分量与 \(G^R\) 的强连通分量相同。
解答来源：dis04-sol.pdf · 4 · confidence: high
题面来源：dis04.pdf · 3 · confidence: high
考虑任意一个无向连通图 \(G = (V, E)\)。若删除边 \((u, v) \in E\) 会使图不再连通，则称该边为关键边（critical edge）。换句话说，图 \((V, E \setminus \{(u, v)\})\) 不再连通。类似地，若删除顶点 \(v \in V\) 及其所有关联边后图不再连通，则称 \(v\) 为关键顶点（critical vertex）。
(a) 是否总能找到一个非关键顶点 \(v \in V\)？非关键边呢？
(b) 给出一个线性时间算法，找出 \(G\) 的所有关键边。
(c) 修改上述算法，找出 \(G\) 的所有关键顶点。
(d) \(G\) 的一个双连通分量是指不包含关键顶点的连通子图；换句话说，从该分量中删除任意一个顶点后，它仍保持连通。若将 \(G\) 的所有双连通分量收缩为超节点（meta-node）（类似于对 SCC 的操作），所得结果图具有什么性质？
示例图：无向连通图 G = (V, E)，例如 V = {a, b, c, d, e}，E = {(a,b), (a,c), (b,c), (c,d), (d,e)}
DFS 树边（实线）与回边（虚线）
每个顶点标注 pre[v]/low[v] 值
关键边标记（满足 low[child] > pre[parent] 的树边）
关键顶点标记（根节点有多个子节点，或某子节点 low > pre）
来源：dis04-sol.pdf · 4
从 DFS 树的叶子入手思考非关键顶点；利用 low-link 值判断关键边/顶点；收缩后的结构可通过反证法证明。
(a) 在图上从任意顶点运行 DFS，取所得 DFS 树中的任意一个叶子。删除该叶子不会使图不连通，因为剩余顶点仍通过 DFS 树边相连。但我们不一定能找到非关键边。例如，树中的每条边都是关键边。
(b) 在 \(G\) 上运行 DFS，记录每个顶点的 \(\text{pre}[v]\)。同时维护每个顶点的 \(\text{low}\) 值，其中 \(\text{low}[v]\) 表示 \(v\) 的子树中通过一条回边可达的顶点 \(u\) 的最小 \(\text{pre}[u]\)。唯一可能的关键边是 DFS 中的树边。\(v\) 与其父节点 \(p\) 之间的边是关键边，当且仅当 \(\text{low}[v] > \text{pre}[p]\)（即不存在从 \(v\) 到 \(p\) 或其任意祖先的回边）。
复杂度：\(O(|V| + |E|)\)，与标准 DFS 相同。
(c) DFS 树的根节点是关键顶点，当且仅当它有多于一个子节点。非根顶点 \(v\) 是关键顶点，当且仅当存在 \(v\) 的某个子节点 \(c\) 满足 \(\text{low}[c] > \text{pre}[v]\)。
复杂度：\(O(|V| + |E|)\)，与 (b) 相同。
(d) 所得结果图是一棵树。为证明这一点，可证：若结果图中存在环，则该环上所有超节点都属于同一个双连通分量，导致矛盾。
解答来源：dis04-sol.pdf · 4 · confidence: high
题面来源：dis04.pdf · 3 · confidence: high
给定一个强连通的有向图 \(G = (V, E)\)，边权为正，以及一个特殊节点 \(v_0 \in V\)。请设计一个高效算法，对所有节点对 \(s, t\)，计算从 \(s\) 到 \(t\) 且必须经过 \(v_0\) 的最短路径长度。
你的算法时间复杂度应为 \(O(|V|^2 + |E| \log |V|)\)。
提示：考虑将必须经过 \(v_0\) 的路径拆分为两段。如何高效地同时得到所有节点到 \(v_0\) 的距离，以及 \(v_0\) 到所有节点的距离？
从 \(s\) 到 \(t\) 且经过 \(v_0\) 的最短路径长度，等于从 \(s\) 到 \(v_0\) 的最短路径长度加上从 \(v_0\) 到 \(t\) 的最短路径长度：
\[\text{dist}_{v_0}(s, t) = \text{dist}(s, v_0) + \text{dist}(v_0, t)\]
算法步骤设 \(P\) 是一条从 \(s\) 到 \(t\) 且经过 \(v_0\) 的最短路径。由于路径必须经过 \(v_0\)，\(P\) 可分解为子路径 \(P_1\)（从 \(s\) 到 \(v_0\)）和子路径 \(P_2\)（从 \(v_0\) 到 \(t\)）。
\(P_1\) 的长度 \(\geq\) 从 \(s\) 到 \(v_0\) 的最短距离 \(d_G(s, v_0)\)。
\(P_2\) 的长度 \(\geq\) 从 \(v_0\) 到 \(t\) 的最短距离 \(d_G(v_0, t)\)。
因此 \(|P| \geq d_G(s, v_0) + d_G(v_0, t)\)。
反之，取一条从 \(s\) 到 \(v_0\) 的最短路径和一条从 \(v_0\) 到 \(t\) 的最短路径拼接起来，就得到一条从 \(s\) 到 \(t\) 且经过 \(v_0\) 的路径，其长度恰好为 \(d_G(s, v_0) + d_G(v_0, t)\)。
故 \(\text{dist}_{v_0}(s, t) = d_G(s, v_0) + d_G(v_0, t)\)。
复杂度分析两次 Dijkstra 调用：\(O((|V| + |E|) \log |V|)\)。
枚举所有点对：\(O(|V|^2)\)。
总时间复杂度：\(O(|V|^2 + |E| \log |V|)\)，满足要求。
解答来源：dis04-sol.pdf · 5-6 · confidence: high
题面来源：dis04.pdf · 4 · confidence: high
你需要在伯克利完成 \(k\) 件差事。伯克利被表示为一个有向加权图 \(G\)，其中每个顶点 \(v\) 是一个地点，边 \((u, v)\) 的权重 \(w_{uv}\) 表示从 \(u\) 到 \(v\) 需要 \(w_{uv}\) 分钟。
差事必须按顺序完成：第 \(i\) 件差事在访问集合 \(S_i\) 中的任意一个顶点时即可立即完成（例如，若需购买零食，可在任意超市完成）。你的家位于顶点 \(h\)。
给定 \(G, h\) 以及所有的 \((S_i)_{i=1}^k\)，设计一个高效算法，计算从家 \(h\) 出发完成所有差事所需的最少时间（分钟）。即，在 \(G\) 中找到一条从 \(h\) 出发的最短路径，使其依次经过 \(S_1\) 中的一个顶点、然后 \(S_2\) 中的一个顶点、然后 \(S_3\) 中的一个顶点，依此类推。
例如在下图中，最短路径为 \(h \to C \to B \to C \to E\)，所需时间为 \(5 + 3 + 4 + 10 = 22\)。
（图：包含节点 \(h, A, B, C, D, E, F\) 的有向加权图，集合 \(S_1, S_2, S_3\) 标注在部分节点上。）
\(h\)（家）
\(A, B, C, D, E, F\)
\(h \to C\)：5
\(C \to B\)：3
\(B \to C\)：4
\(C \to E\)：10
其他边权重包括 2, 4, 9, 10 等（具体拓扑参考原图）
最短路径：\(h \to C \to B \to C \to E\)
总时间：\(5 + 3 + 4 + 10 = 22\)
来源：dis04.pdf · 5
提示：如果每个顶点不仅有位置信息，还带有"已完成前若干件差事"的状态，图的结构会如何变化？
构建一个分层图 \(G'\)，共 \(k+1\) 层，分别记为 \(G_0, G_1, \ldots, G_k\)。每层是原图 \(G\) 的一个拷贝，\(G_i\) 中顶点 \(v\) 的拷贝记为 \(v_i\)。
对于每个 \(v \in S_i\)，添加一条从 \(v_{i-1}\) 到 \(v_i\) 的权值为 0 的边。
算法步骤引理：\(G'\) 中从 \(h_0\) 到 \(G_k\) 中任意顶点的路径，与 \(G\) 中从 \(h\) 出发按顺序经过 \(S_1, S_2, \ldots, S_k\) 的路径一一对应，且长度相同。
证明：将 \(G'\) 中的路径映射回 \(G\)：对每条边 \((u_i, v_i)\)，替换为 \(G\) 中的边 \((u, v)\)；忽略形如 \((v_{i-1}, v_i)\) 的零权边。所得路径长度不变。由于路径必须依次包含形如 \((v_0, v_1), (v_1, v_2), \ldots\) 的边，因此对应的路径按顺序经过了 \(S_1, S_2, \ldots, S_k\)。
反之，\(G\) 中任何按顺序完成差事的路径，都可以在 \(G'\) 中找到对应的、长度相同的路径。
因此，\(G'\) 中从 \(h_0\) 到 \(G_k\) 的最短路径长度等于原问题的最优解。
复杂度分析分层图 \(G'\) 的规模为原图的 \(k+1\) 倍：
顶点数：\((k+1)|V|\)
边数：\((k+1)|E| + k|V|\)
在 \(G'\) 上运行 Dijkstra 的时间为 \(O(k(|V| + |E|) \log k|V|)\)。
解答来源：dis04-sol.pdf · 7 · confidence: high
题面来源：dis04.pdf · 5 · confidence: high
提示：助教可能不会在课堂上覆盖全部题目，这很正常。讨论讲义并非设计为一小时内做完，而是有意保留较长篇幅，供你在课后练习、巩固并拓展讲课、阅读与作业中的概念。
5 图的遍历（选做）
下图是一个包含顶点 \(A, B, C, D, E, F, G, H, I, J\) 的有向图（详见 dis04.pdf 第 5 页图）。
(a) 回顾 DFS 树中的边可以分为四种类型：
树边（Tree edges）：DFS 树中的边；
后向边（Back edges）：不在 DFS 树中的边 \((u, v)\)，其中 \(v\) 是 \(u\) 在 DFS 树中的祖先；
前向边（Forward edges）：不在 DFS 树中的边 \((u, v)\)，其中 \(u\) 是 \(v\) 在 DFS 树中的祖先；
横叉边（Cross edges）：不在 DFS 树中的边 \((u, v)\)，其中 \(u\) 不是 \(v\) 的祖先，\(v\) 也不是 \(u\) 的祖先。
对上面的有向图从顶点 A 开始执行 DFS，按字母顺序打破平局。在遍历过程中，为每个节点标注 pre-number 和 post-number，并将每条边标记为 Tree、Back、Forward 或 Cross。
(b) 强连通分量（SCC）定义为顶点的一个子集，其中从每个顶点到其他任意顶点都存在路径。求上图的所有 SCC。
(c) 将 (b) 中找到的每个 SCC 收缩为一个 meta-node，得到由 SCC meta-node 构成的图。在下方画出这个图，并描述其结构。
顶点：A, B, C, D, E, F, G, H, I, J 边：A→B, A→E, C→J, J→F, F→D, F→H, H→I, I→G, G→H, D→C, D→A, H→A, E→B
来源：dis04.pdf · 5
DFS 树边（实线）：A→B, A→E, C→J, J→F, F→D, F→H, H→I, I→G 后向边（虚线，Back）：G→H, D→C 横叉边（虚线，Cross）：D→A, H→A, E→B pre/post 号码：A(1,6), B(2,3), C(7,20), D(10,11), E(4,5), F(9,18), G(14,15), H(12,17), I(13,16), J(8,19)
来源：dis04-sol.pdf · 8
Meta-nodes：{A}, {B}, {E}, {G,H,I}, {C,J,F,D} 边：{C,J,F,D}→{G,H,I}, {C,J,F,D}→{A}, {G,H,I}→{A}, {A}→{E}, {A}→{B}, {E}→{B}
来源：dis04-sol.pdf · 9
提示：
DFS 从 A 开始，按字母顺序访问邻居。注意 pre-number 在首次访问节点时分配，post-number 在节点的所有邻居处理完毕后分配。
判断边类型时，关键是看目标节点与源节点在 DFS 树中的祖先-后代关系。
对于 SCC，考虑每个节点能到达哪些节点，以及哪些节点能到达它。互相可达的节点属于同一个 SCC。
收缩 SCC 后得到的 meta-graph 一定是有向无环图（DAG）。
(a) DFS 遍历结果
从顶点 A 开始，按字母顺序打破平局，DFS 的 pre-number 和 post-number 如下：
| 顶点 | pre-number | post-number |
|---|---|---|
| A | 1 | 6 |
| B | 2 | 3 |
| C | 7 | 20 |
| D | 10 | 11 |
| E | 4 | 5 |
| F | 9 | 18 |
| G | 14 | 15 |
| H | 12 | 17 |
| I | 13 | 16 |
| J | 8 | 19 |
边分类：
树边（Tree）：A→B, A→E, C→J, J→F, F→D, F→H, H→I, I→G
后向边（Back）：G→H（H 是 G 的祖先）, D→C（C 是 D 的祖先）
横叉边（Cross）：D→A, H→A, E→B
前向边（Forward）：无
证明： DFS 从 A(1) 开始，先访问 B(2)，B 无未访问邻居，B 结束于 3。回到 A，访问 E(4)，E 的邻居 B 已访问，E 结束于 5。A 的邻居处理完毕，A 结束于 6。下一个未访问节点 C(7)，C→J(8)，J→F(9)，F→D(10)，D 的邻居 C 和 A 均已访问，D 结束于 11。回到 F，F→H(12)，H→I(13)，I→G(14)，G 的邻居 H 已访问，G 结束于 15。依次回溯，I 结束于 16，H 结束于 17，F 结束于 18，J 结束于 19，C 结束于 20。
边类型判断依据：
G→H：H(12,17) 是 G(14,15) 的祖先（DFS 树路径 H→I→G），故为后向边。
D→C：C(7,20) 是 D(10,11) 的祖先（DFS 树路径 C→J→F→D），故为后向边。
D→A：A(1,6) 与 D(10,11) 的区间不重叠，互不为祖先，故为横叉边。
H→A：A(1,6) 与 H(12,17) 的区间不重叠，互不为祖先，故为横叉边。
E→B：B(2,3) 与 E(4,5) 的区间不重叠，互不为祖先，故为横叉边。
(b) 强连通分量
SCCs 为：\(\{A\}\), \(\{B\}\), \(\{E\}\), \(\{G, H, I\}\), \(\{C, J, F, D\}\)
证明：
\(\{G, H, I\}\)：H→I, I→G, G→H 形成环，三者互相可达。
\(\{C, J, F, D\}\)：C→J→F→D→C 形成环，四者互相可达。
\(\{A\}\)：A 可到达 B 和 E，但 B 和 E 无法到达 A（B 无出边，E 只指向 B），故 A 独立。
\(\{B\}\)：B 无出边，无法到达任何其他节点，故独立。
\(\{E\}\)：E→B，但 B 无法到达 E，故 E 独立。
(c) Meta-graph
将每个 SCC 收缩为 meta-node，meta-graph 的边为：
\(\{C,J,F,D\} \to \{G,H,I\}\)（来自 F→H）
\(\{C,J,F,D\} \to \{A\}\)（来自 D→A）
\(\{G,H,I\} \to \{A\}\)（来自 H→A）
\(\{A\} \to \{E\}\)（来自 A→E）
\(\{A\} \to \{B\}\)（来自 A→B）
\(\{E\} \to \{B\}\)（来自 E→B）
结构描述： Meta-graph 是一个有向无环图（DAG）。拓扑序为 \(\{C,J,F,D\}\), \(\{G,H,I\}\), \(\{A\}\), \(\{E\}\), \(\{B\}\)。\(\{C,J,F,D\}\) 和 \(\{G,H,I\}\) 均有边指向 \(\{A\}\)，\(\{A\}\) 有边指向 \(\{E\}\) 和 \(\{B\}\)，\(\{E\}\) 有边指向 \(\{B\}\)。
复杂度分析： DFS 遍历的时间复杂度为 \(O(V + E)\)，其中 \(V = 10\) 为顶点数，\(E = 13\) 为边数。识别 SCC 的算法（如 Kosaraju 或 Tarjan）同样为 \(O(V + E)\)。收缩 SCC 并构建 meta-graph 的过程也是 \(O(V + E)\)。
解答来源：dis04-sol.pdf · 8-9 · confidence: high
题面来源：dis04.pdf · 5-6 · confidence: high
6. Dijkstra 算法在负权边上的失效（选做）
请画出一张至多含五个顶点的图，并标明运行 Dijkstra 算法时采用的源点。
(a) 画一张不含负权环、但 Dijkstra 算法会给出错误答案的图。
(b) 画一张至少含两条负权边、但 Dijkstra 算法仍会给出正确答案的图。
Vertices: A, B, C, D
Edges:
- A → B (weight 2)
- B → C (weight -2)
- A → C (weight 1)
- C → D (weight 1)
Source: A
来源：dis04-sol.pdf · 1
Vertices: A, B, C
Edges:
- A → B (weight -1)
- B → C (weight -2)
Source: A
来源：dis04-sol.pdf · 1
Hint for (a): 考虑Dijkstra算法贪心选择最小距离节点且不再重新访问的特性。一条负权边可能产生一条通往已访问节点的更短路径，但Dijkstra算法不会重新检查该节点。
Hint for (b): 考虑一条简单的有向路径，其中每个节点按顺序被访问，不存在需要重新访问已确定节点的替代路径。
(a) Here's one example:
A
B
C D
2 -2
1 1
More precisely, the graph has vertices \(A\), \(B\), \(C\), \(D\) and directed edges:
\(A \to B\) with weight \(2\)
\(B \to C\) with weight \(-2\)
\(A \to C\) with weight \(1\)
\(C \to D\) with weight \(1\)
从源点 \(A\) 运行 Dijkstra 算法时，由于先访问 \(C\) 后访问 \(B\)，算法会把到 \(D\) 的距离误算为 \(2\)，而真实最短距离是 \(1\)。
(b) 在有向路径图上，Dijkstra 算法始终能正确工作。例如：
A → B → C
-1 -2
More precisely, the graph has vertices \(A\), \(B\), \(C\) and directed edges:
\(A \to B\) with weight \(-1\)
\(B \to C\) with weight \(-2\)
Dijkstra's algorithm from source \(A\) correctly computes: \(d(B) = -1\), \(d(C) = -3\).
解答来源：dis04-sol.pdf · 1 · confidence: high
题面来源：dis04.pdf · 1 · confidence: high
提示： 你的助教可能不会覆盖所有问题。这完全没问题，讨论课讲义并非设计在一小时内完成。它们故意出得很长，以便作为资源供你练习、巩固和拓展课堂、阅读和作业中讨论的概念。
在本问题中，我们将考虑最短路径问题：给定图 \(G(V, E)\)，找出从 \(s\) 到每个顶点 \(v \in V\) 的最短路径长度。对于无权图，路径长度是路径中边的数量。我们可以使用广度优先搜索（BFS）算法来解决这个问题，本周课上还会再次讲到。
BFS 可以像深度优先搜索（DFS）一样实现，但使用队列而非栈。下面是 BFS 的另一种实现的伪代码，它对每个 \(i \in \{0, 1, \ldots, |V| - 1\}\) 计算距离 \(s\) 为 \(i\) 的顶点集合，记为 \(L_i\)。
Algorithm 1 Vertex Distances via BFS
visited(v) = Falsevisited(s) = Truevisited(v) = False thenvisited(v) = True换句话说，我们从 \(L_0 = \{s\}\) 开始，然后对每个 \(i\)，将 \(L_{i+1}\) 设为 \(L_i\) 中顶点的所有尚未加入之前任何 \(L_j\)（\(j \le i\)）的邻居。
(a) 证明 BFS 对所有 \(i\) 都计算出正确的 \(L_i\) 值。
(b) 证明该算法与 DFS 一样，运行时间为 \(O(m + n)\)，其中 \(n\) 是节点数，\(m\) 是边数。
(c) 我们可能想找出从 \(s\) 到每个顶点的最短加权路径。即每条边有权重 \(w_e\)，路径长度是路径中边的权重之和。上述算法在所有 \(w_e = 1\) 时有效，但如果某些 \(w_e \neq 1\) 则容易出错。
填空以得到一个在 \(w_e\) 为正整数时计算最短路径的算法：
我们将 \(G\) 中的每条边 \(e\) 替换为 __ 得到新图 \(G'\)，然后在 \(G'\) 上从 \(s\) 开始运行 BFS。证明你的答案。
(d) 该算法作为权重 \(w_e\) 的函数，运行时间是多少？写出所有 \(w_e\) 需要多少位？该算法的运行时间是否是输入规模的多项式？
有向图示例：原边 e 被替换为 we 条连续无权边构成的路径
来源：dis04-sol.pdf · 11
(a) 提示：使用归纳法证明，对所有 \(i\)，\(L_i\) 包含所有距离 \(s\) 为 \(i\) 的顶点，且仅包含这些顶点。
(a) 解： 我们声称在 for 循环的第 \(i\) 次迭代开始前：(1) 所有距离 \(s\) 恰好为 \(i\) 的顶点都在 \(L_i\) 中，(2) 所有距离 \(s\) 大于 \(i\) 的顶点尚未被加入任何 \(L_j\)（\(j \le i\)）。我们将归纳证明这对所有 \(i\) 成立，从而说明算法是正确的。
这对 \(i = 0\) 成立。假设对 \(i = k\) 成立。我们证明对 \(i = k + 1\) 成立。(1) 对 \(i = k + 1\) 成立是因为每个距离为 \(k + 1\) 的顶点都与某个距离为 \(k\) 的顶点相邻，因此由归纳假设 (1)，它会在第 \(k\) 次迭代中被加入 \(L_{k+1}\)。(2) 成立是因为没有距离为 \(k + 2\) 或更远的顶点能与距离为 \(k\) 或更小的顶点相邻，因此在第 \(k\) 次迭代中加入任何 \(L_{k+1}\) 的顶点只能是那些距离恰好为 \(k + 1\) 的顶点。
(b) 解： 初始化 visited 花费 \(O(n)\) 时间。for 循环的第 \(i\) 次迭代花费 \(O\!\left(\sum_{v \in L_i} \delta(v)\right)\) 时间，其中 \(\delta(v)\) 是 \(v\) 的度。由于没有 \(v\) 出现在多个 \(L_i\) 中，总时间为 \(O\!\left(n + \sum_{v \in V} \delta(v)\right) = O(n + m)\)。
(c) 解： 一条由 \(w_e\) 条无权边组成的路径。见下图示例（有向图）：
图示：有向图中，原权重为 \(w_e\) 的边 \(e\) 被替换为 \(w_e\) 条连续无权边构成的路径。
(d) 解： 运行时间为 \(O\!\left(\sum_{e \in E} w_e\right)\)，因为 \(G'\) 有 \(\sum_{e \in E} w_e\) 条边。所需位数为 \(\Theta\!\left(\sum_{e \in E} \log w_e\right)\)。因此，尽管该算法的运行时间看起来像多项式，但当某些 \(w_e\) 很大时，它花费的时间是指数级于输入规模的。
解答来源：dis04-sol.pdf · 10-12 · confidence: high
题面来源：dis04.pdf · 7-8 · confidence: high
dis04.pdfdis04-sol.pdf