The Proof of Correctness of Some of the Shortest Path Algorithms

2022-03-05T18:41:00

本文只对算法导论中文第 3 版中 Bellman-FordDijkstraFloyd-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 -> ... -> vs ~ 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. up 上,则根据引理 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,只要从 v1vk 按顺序对其上所有边依次松弛一遍,最终 d[vi] == dmin[vi]

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

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

p384 定理 24.6 Dijkstra 算法的正确性

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

证明:

归纳法

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

假设 u 是第一个加入 S 不满足 d[u] == dmin[u] 的点。如果存在最短路径 s -> ... -> x -> y -> ...-> u,其中 s ~ x 都在集合 Sy ~ u 都不在,xy 的直接前驱。根据假设,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 每次只会选集合 Sd 最小的点,u 被选中,yu 又都在 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} 的权值最小路径。pp' 满足如下关系:

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

d[i][j][k] 是所有中间结点都来自集合 Ai ~ 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
当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »