本文只对算法导论中文第 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)
证明：
- 若
u在p上，则根据引理 24.1，等号成立 若
u不在p上u所在路径是另一条s ~ v最短路径，此时等号成立u所在路径不是s ~ v最短路径，不等号成立
实际上，即使 s ~ v 不存在最短路径，该不等式也成立
- 若
dmin[v] = +oo，即s ~ v不可达，则dmin[u] = +oo，等号成立 - 若
dmin[v] = -oo，即s ~ v存在负权环，则证明过程类似上述s ~ v存在最短路径的情况
因此该不等式总是成立
p391 引理 24.11：上界性质
初始化完成后，对于所有节点 v，在松弛过程中 d[v] >= dmin[v] 一直成立。且在等号成立后，d[v] 不再变化
证明：
归纳法
- 基础步。初始化后，
d[v] >= dmin[v]成立 - 归纳步。考虑对边
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]
证明：
归纳法
- 初始状态。加入起点
v0，d[v0] == 0 == dmin[v0] - 保持。反证法
假设 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' 满足如下关系：
- 如果结点
k不是p的中间结点，则p的所有中间结点都来自集合B。所以p'可以作为p，即所有结点都取自集合A的最短路径等于所有中间结点都来自集合B的最短路径 - 如果
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如有问题请在下方留言，文章转载请注明出处，详细交流请加下方群组！请大佬不要屏蔽文中广告，因为它将帮我分担服务器开支，如果能帮忙点击我将万分感谢。