## Exercise 1

每个节点只入一次队，每条边也只遍历一次，故复杂度是$(O(|V|+|E|))$，是线性的。

Exercise 2

![[7f57f02ea91bd04172d9416821211011_720.jpg]]
![[6bdfed81d8a6ba5ccaf135c1b2eaa228.jpg]]

(a)

$E,B,A,(H,I,G),(C,J,F,D)$

(b)

source: $B,E$
sink: $(C,D,F,J)$

(c)

![[d0a6e1aadc189f0a5b8eec10d88a728e_720.jpg]]

(d)

6
由metagraph可知，我对这张图中的边添加一条反边就能合并两个强连通分量。故最少添加6条边。

Exercise 3

(a)

(b)

![[e643af3c4d2a6c16b8f5e73806177ea6.jpg]]

Exercise 4

![[9f269e84be671249eb21d12267859ebb_720.jpg]]
由DFS树可以算出最短环应该是4
但是如图很明显最短环是3
此即反例

Exercise 5

Base Case

在循环开始前（初始化），$dist(s) = 0$，其余所有节点的 $dist = \infty$。

进入第 1 次循环：
算法在第 4 行必然选中节点 。
第 5 行将其加入集合，此时 $R_1 = \{s\}$。
第 6-8 行遍历 $s$ 的所有出边 $(s, z)$，更新 $dist_1(z) = l(s, z)$。如果不与 $s$ 直接相邻，则仍为 $\infty$。

对条件 (1)：
取 $d = 0$。
$R_1$ 中唯一的节点是 $s$，其到 $s$ 的距离为 $0 \le d$。
$R_1$ 之外的所有节点到 $s$ 的真实距离由于边权非负，均 $\ge 0 = d$。条件 (1) 成立。

对条件 (2)：

此时，路径的中间节点被限制在 $R_1 = \{s\}$ 中。
对于任意节点 $u \neq s$，从 $s$ 到 $u$ 且中间节点只能是 $s$ 的路径，实际上就是不包含任何其他中间节点的直接相连边 $(s, u)$。
这种路径的最短长度正好是 $l(s, u)$（不存在直接边则为 $\infty$）。
这与第 6-8 行的更新操作结果 $dist_1(u)$ 完全一致。条件 (2) 成立。

Inductive Hypothesis

假设在第 $k$ 次迭代结束时，条件 (1) 和 (2) 均成立。即：
存在 $d_k$，使得 $\forall x \in R_k, \delta(s, x) \le d_k$，且 $\forall y \notin R_k, \delta(s, y) \ge d_k$。
对于所有节点 $u$，$dist_k(u)$ 记录了：从起点 $s$ 到 $u$、且中间节点全部约束在 $R_k$ 中的最短路径长度。

Inductive Step

在第 $k+1$ 次迭代中：
算法从 $V \setminus R_k$ 中选择了一个 $dist$ 值最小的节点，记为 $v^{}$。
将 $v^{}$ 加入 $R$，得到 $R_{k+1} = R_k \cup \{v^{*}\}$。

对条件 (1)：
取 $d_{k+1} = dist_k(v^{})$。
根据归纳假设的条件 (2)，$dist_k(v^{})$ 是中间节点受限于 $R_k$ 时的最短路径。由于每次选择的都是 $V \setminus R_k$ 中的最小值，且所有边权 $\ge 0$，这条路径就是从 $s$ 到 $v^{}$ 的全局真实最短路径，即 $\delta(s, v^{}) = d_{k+1}$。
如果存在更短路径，必然要从 $R_k$ 经过某个 $y \notin R_k$ 到达 $v^{}$，而 $dist_k(y) \ge dist_k(v^{})$，由于边权非负，距离不可能越走越短，故矛盾。
对于 $R_{k+1}$ 中的原节点 $u \in R_k$，已知 $\delta(s, u) \le d_k \le d_{k+1}$。所以 $R_{k+1}$ 中的所有节点距离均 $\le d_{k+1}$。
对于 $R_{k+1}$ 之外的任意节点 $w$，到达 $w$ 的最短路径必经过至少一个属于 $V \setminus R_k$ 的节点。设该路径离开 $R_k$ 后到达的第一个节点是 $y$，则 $\delta(s, w) \ge \delta(s, y) = dist_k(y)$。由于算法挑出了最小值 $v^{}$，必有 $dist_k(y) \ge dist_k(v^{}) = d_{k+1}$。因此，所有在 $R_{k+1}$ 之外的节点距离 $\ge d_{k+1}$。
取 $d = d_{k+1}$，条件 (1) 满足。

对条件 (2)：
当集合从 $R_k$ 扩展为 $R_{k+1} = R_k \cup \{v^{}\}$ 时，我们需要考虑任何到达节点 $z$ 的新约束路径。
从 $s$ 到 $z$ 且中间节点仅限于 $R_{k+1}$ 的最短路径，只可能有以下两种情况：
1. 不经过新加入的 $v^{}$ 作为中间节点： 那么中间节点全在 $R_k$ 中。根据归纳假设，这种路径的最短长度就是现有的 $dist_k(z)$。
2. 经过 $v^{}$ 作为中间节点： 因为 $v^{}$ 的最短路径 $\delta(s, v^{}) = dist_k(v^{})$ 已经确定，这条路径必定是由“从 $s$ 到 $v^{}$ 的最短路径（仅用 $R_k$）与$(v^{}, z)$拼接而成。其长度为 $dist_k(v^{}) + l(v^{}, z)$。
以 $R_{k+1}$ 为中间节点的全局最短路径，必然是这两种情况中的较小值：

这与第 7-8 行操作一致：
因此，第 $k+1$ 次迭代结束时，数组更新正确。条件 (2) 成立。

故知两个条件均满足

Exercise 5 - new version

归纳奠基： dist(s) = 0， 其余的 dist(·) = $\infty$
第一次循环一定会将 s 加入 R ，并更新 s 的所有出边。此时的两个性质：
(1) ：R 中的点（只有 s）的dist $\leq 0$ ，R 以外的点由于边权非负一定 $>0$
(2) ：R 中只有 s ，故最短路径被限制在 R 中。

归纳假设：
完成第 k 次循环，此时的两个性质：
(1)：存在一个 $d_{k}$，使得 dist$(u \in R)\leq d_{k}$，dist$(u \not\in R)\geq d_{k}$
(2)：对任意dist不是$\infty$的点u，dist(u)都是中间点限制在 R 中的最短路径长度

归纳递推：
对于第 k+1 次循环，加入第 k+1 个点，记该点为 c ，并更新了这个点相关的所有出边，此时两个性质：
(1)：由归纳假设知，dist(c) $\geq d_{k}$，即dist(c) 比所有在 R 中节点的 dist都大，且有选取条件知，dist(c) 是所有不在 R 中节点中dist最小的，所以取 $d_{k+1}=$dist(c)，则有性质(1):

(2)：对于此次更新未涉及到的节点，有归纳假设可知一定满足性质，故可以只考虑本次更新节点，即 c 的出边涉及到的节点，分为两种情况考虑：

1. 没能成功更新u：如果中间点限制在 R 中且经过 c 比没有经过 c 长，所以之前的路径仍然是中间点限制在 R 中的最短路径。
2. 成功更新u：中间点限制在 R 中且经过 c 比没有经过 c 短，且已知 dist$(c)$ 就是中间点限制在 R 中的抵达 c 的最短路径，那么只需说明dist(u)=dist(c)+l(c,u)就是中间点限制在R中且经过c的最短路径。若存在点 $v \in R$ 使得 $c \to v \to u$ 比 $c\to u$更短，那么 dist$(v)$应该$\geq$ dist(c)，不然根本没有办法通过dist(c)来更新dist(v)（由于边权非负），而这正与性质(1)矛盾。所以dist(u)=dist(c)+l(c,u)就是中间点限制在R中且经过c的最短路径，也是中间点限制在R中的最短路径。