The Proof of Correctness of Some of the Shortest Path Algorithms

本文只对算法导论中文第 3 版中 Bellman-Ford，Dijkstra，Floyd-Warshall 算法的正确性证明进行非严谨重述。这些证明对堆优化版 Dijkstra 和队列优化版 Bellman-Ford，即 SPFA 同样适用，因为它们和原版没有本质不同

p374 单源最短路径

记 V 为图 G 所有点构成的集合，d[v] 为 s ~ v 最短距离的估计值，dmin[v] 为实际值，s 是起点，v 是终点，w(u, v) 是边 u -> v 的权重

p375 引理 24.1：最短路径的子路径也是最短路径

如果 s -> ... -> x -> ... -> y -> ... -> v 是 s ~ v 的一条最短路径，则 x -> ... -> y 也是 x ~ y 的一条最短路径

证明：

如果能找到 x ~ y 的一条更短路径，则前述 s ~ v 的路径也不能称最短

p391 引理 24.10：三角不等式性质

如果 s ~ v 存在最短路径 p，则对于任何边 u -> v 一定满足 dmin[v] <= dmin[u] + w(u, v)

证明：

1. 若 u 在 p 上，则根据引理 24.1，等号成立

2. 若 u 不在 p 上

   1. u 所在路径是另一条 s ~ v 最短路径，此时等号成立
   2. u 所在路径不是 s ~ v 最短路径，不等号成立

实际上，即使 s ~ v 不存在最短路径，该不等式也成立

1. 若 dmin[v] = +oo，即 s ~ v 不可达，则 dmin[u] = +oo，等号成立
2. 若 dmin[v] = -oo，即 s ~ v 存在负权环，则证明过程类似上述 s ~ v 存在最短路径的情况

因此该不等式总是成立

p391 引理 24.11：上界性质

初始化完成后，对于所有节点 v，在松弛过程中 d[v] >= dmin[v] 一直成立。且在等号成立后，d[v] 不再变化

证明：

归纳法

1. 基础步。初始化后，d[v] >= dmin[v] 成立
2. 归纳步。考虑对边 u -> v 松弛，松弛前 d[u] >= dmin[u]，如果松弛失败，条件不变。如果成功有 d[v] = d[u] + w(u, v) >= dmin[u] + w(u, v) >= dmin[v]（结合引理 24.10），条件仍然成立

因此上界可一直保持。又因为等号成立后，松弛都不会成功，所以 d[v] 不再变化

p392 引理 24.14：收敛性质

如果 s -> ... -> u -> v 是一条最短路径，松弛前 d[u] == dmin[u]，则松弛后有 d[v] <= d[u] + w(u, v) = dmin[u] + w(u, v) = dmin[v]（结合引理 24.1）。根据引理 24.11 有 d[v] >= dmin[v]，结合前一不等式得 d[v] == dmin[v]

p392 引理 24.15：路径松弛性质

如果存在一条最短路 v1 -> ... -> vk，初始化完成后，根据引理 24.14，只要从 v1 到 vk 按顺序对其上所有边依次松弛一遍，最终 d[vi] == dmin[vi]

p380 引理 24.2：Bellman-Ford 算法循环次数的合理性

如果存在一条包含 n 个节点的最短路 v1 -> ... -> vn，规定最短路是简单路，点与点依次相连，则该路径有 n-1 条边。BF 算法第 i 次循环会松弛边 vi -> vi+1。n - 1 次循环即达成上述路径松弛性质

p384 定理 24.6 Dijkstra 算法的正确性

算法每次循环都会把一个点加入集合 S，只需证明，加入到集合 S 中的点 v，都满足 d[v] == dmin[v]

证明：

归纳法

1. 初始状态。加入起点 v0，d[v0] == 0 == dmin[v0]
2. 保持。反证法

假设 u 是第一个加入 S 不满足 d[u] == dmin[u] 的点。如果存在最短路径 s -> ... -> x -> y -> ...-> u，其中 s ~ x 都在集合 S，y ~ u 都不在，x 是 y 的直接前驱。根据假设，d[x] == dmin[x]。而 x 在加入 S 时，会松弛边 x -> y，根据引理 24.14，d[y] 会变为 dmin[y]，所以 d[u] >= dmin[u] >= dmin[y] == d[y]（结合引理 24.11），即 d[u] >= d[y]。我们知道，Dijkstra 每次只会选集合 S 外 d 最小的点，u 被选中，y，u 又都在 S 外，则 d[u] <= d[y]，合并前述不等式得 d[u] == d[y] == dmin[y] == dmin[u]，这与假设矛盾。所以 d[u] == dmin[u] 也成立

由于初始和保持都成立，所以对于加入到集合 S 中的点 v，都有 d[v] == dmin[v]

p399 多源最短路径

p404 Floyd-Warshall 算法的正确性

假定图 G 所有结点为 V = {1, 2, ..., n}，考虑它的一个子集 A = {1, 2, ..., k}，k 是小于 n 的整数。任取 V 上结点对 (i, j)，记路径 p：i -> ... -> j 是中间结点都取自集合 A 的权值最小路径。另一条路径 p'：i -> ... -> j 是中间结点都取自集合 B = {1, 2, ..., k-1} 的权值最小路径。p 和 p' 满足如下关系：

1. 如果结点 k 不是 p 的中间结点，则 p 的所有中间结点都来自集合 B。所以 p' 可以作为 p，即所有结点都取自集合 A 的最短路径等于所有中间结点都来自集合 B 的最短路径
2. 如果 k 是 p 的中间结点，则 p 可表示为 i -> ... -> k -> ... -> j。记路径 p 的靠前部分 i -> ...-> k 为 p1，靠后部分 k -> ... -> j 为 p2，由引理 24.1，p1, p2 分别是 i ~ k 和 k ~ j 的最短路径。由于 k 不是 p1 的中间结点，它的中间结点都来自集合 B，所以 p1 还是所有结点都来自集合 B 的 i ~ k 最短路径。同理 p2 也是所有结点都来自集合 B 的 k ~ j 的最短路径

记 d[i][j][k] 是所有中间结点都来自集合 A 的 i ~ j 的最短距离。根据以上观察，有

d[i][j][k] = w(i, j), 当 k = 0
d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1]), 当 k >= 1