Bellman–Ford 一节以反复松弛处理任意实数权重,0–1 BFS 一节则利用权重只有 的特性。本节讨论其余情况下最常用的两个通用算法。Dijkstra 算法在所有权重非负时计算单一源点的距离,比 Bellman–Ford 快得多;Floyd–Warshall 则以“允许使用的中间顶点集合”为动态规划的阶段,计算所有有序顶点对之间的距离。两者都依赖同一个基本事实:最短路径由最短路径组成。
1. 设定与约定
定义 16.3.1
(距离与松弛)
设 为有限有向图,、,权重函数 。一条途径的权重是其各边权重之和; 表示从 到 的途径的最小权重,若不可达则为 。无向图把每条边换成两条权重相同的有向边。允许平行边与自环。
松弛。 给定每个顶点的暂定标签 ,松弛边 即:若 ,则令 。全程每个有限标签都是从源点出发的某条真实途径的权重,所以永远有 。
最优子结构。 若 是到 的最小权重途径,则每个前缀 也是到 的最小权重途径;否则以较轻的前缀替换,整条途径便会变轻。
2. Dijkstra 算法
假设。 每条边都满足 。固定源点 。
算法维护标签 与“已确定”顶点集合 ,每次取出标签最小的有限未确定顶点 ,把它确定下来,并松弛 指向未确定顶点的所有出边;已确定顶点的标签不会再改变。用二叉最小堆实现时,堆内存放 (标签, 顶点),取出过时条目时直接舍弃。
for each v: d[v] = infinity; settled[v] = false
d[s] = 0
H = min-heap containing (0, s)
while H is not empty:
(k, u) = extract_min(H)
if settled[u] or k != d[u]: continue # stale entry
settled[u] = true
for each edge (u, v, w):
if not settled[v] and d[u] + w < d[v]:
d[v] = d[u] + w
insert (d[v], v) into H
return d
定义 16.3.2
(已确定顶点与过时条目)
当顶点 从堆中被取出,而取出条目的键等于它当时的标签 时,称 已确定;此后 不再改变。若 已确定,或 ,则堆条目 是过时的;过时条目直接丢弃,不作任何松弛。
定理 16.3.3
(Dijkstra 算法的正确性)
若所有权重非负,则顶点 被确定时有 ;终止时对每个顶点 都有 ,不可达者为 。
证明
(对确定次序作归纳)
对确定顶点的先后次序作归纳,证明每个顶点在被确定的一刻已正确。第一个被确定的是 ,,因为非负图没有负权重途径。
设下一个被确定的是 ,其标签为 ,并设先前已确定的顶点都正确。 是某条途径的权重,故 。假设 以导出矛盾。此时 ;取一条从 到 的最小权重途径 ,令 为 上第一个在确定 之前尚未确定的顶点。 本身未确定,所以 存在;又 ,因此 在 上有已确定的前驱 。由归纳假设 ,而 被确定时边 已被松弛,故其后 。由最优子结构, 到 的前缀是到 的最小权重途径,所以 。于是 ,结合 得 。由于 从 到 的余下部分权重非负,。这表示未确定的 有小于 的有限标签,堆中有键为 的有效条目,与“取出键最小的条目 ”矛盾(若 ,则 ,直接矛盾)。故 。
从 可达的顶点最终都会被确定:否则某条自 出发的路径上有边 , 已确定而 可达但未确定; 被确定时松弛该边,令 得到有限标签及堆内条目,堆未空前它必被取出。不可达顶点永远得不到有限标签。
证明透视
证明在哪里用到非负性
证明只有一步不显然:它不拿 与每个顶点逐一比较,而是沿着最小权重的路径 走,停在第一个尚未确定的顶点 。三个事实在这个边界顶点汇合。(1) 的前驱 已确定,所以由归纳假设 。(2) 被确定时边 已被松弛,故 ,最后一个等号来自最优子结构。(3) 从 到 的尾段权重至少为 ,所以 。(1) 和 (2) 完全没有看过任何权重的正负号,只有 (3) 需要 。三者合起来给出 ,堆会先取出 而不是 ,矛盾。没有非负性时,链条恰好在 (3) 断开;下文负权边一节的输入中就有 。
命题 16.3.4
(二叉堆 Dijkstra 的开销)
采用惰性删除与二叉最小堆的 Dijkstra 算法至多向堆插入 个条目,时间为 ,空间为 。
证明
(计算确定次数与堆条目数)
每个顶点只被确定一次,所以每条边至多被松弛一次。每次成功松弛插入一个堆条目,故堆至多收到 个条目,每次插入或取出耗时 。总时间为 ;当 且无平行边时即 。空间为 。若改用数组扫描代替堆,时间为 ,对非常稠密的图更合适。
3. 例题:含过时条目的 Dijkstra
例题 16.3.5
(含过时堆条目的 Dijkstra)
边:(4)、(1)、(2)、(1)、(5)、(3)、(6)。
| 取出 | 动作 | 其后的堆 |
|---|---|---|
| 确定 ;、 | ||
| 确定 ; 由 改进为 ; | ||
| 确定 ; 由 改进为 ; | ||
| 过时, 已确定 | ||
| 确定 ; 由 改进为 | ||
| 过时 | ||
| 确定 | ||
| 过时 | 空 |
距离为 、、(经 ,而非权重 4 的直接边)、、,路径为 。
4. 为什么负权边会令 Dijkstra 失效
反例模式
负权边令 Dijkstra 失效
声称:只要图中没有负圈,即使部分边权为负,Dijkstra 算法仍会输出正确的距离。
取边 (2)、(3)、(−2)。Dijkstra 先确定 ,再确定标签为 2 的 ,然后确定标签为 3 的 。边 本应给出 ,但 已确定,标签不再被重新检视,所以输出 ,而真实距离是 。在证明中,途径 正是 ,未确定顶点 满足 :尾段 权重为负,不等式 不成立。把所有权重加上同一个常数来消去负数也不能补救,因为边数较多的路径会被不成比例地惩罚。
正确的陈述必须保留假设 。权重可为负而没有负圈时,改用 Bellman–Ford;全点对情形则用下文的 Floyd–Warshall。
5. Floyd–Warshall
定义 16.3.6
(限制中间顶点的最短路径)
把顶点编号为 。定义 为从 到 、所有中间顶点都落在 内的简单路径的最小权重(空路径使 ),不存在则为 。 时不允许任何中间顶点:
平行边取权重最小者。假设: 没有负圈(权重本身可以为负)。
定理 16.3.7
(Floyd–Warshall 递推式)
若 没有负圈,则对每个 及所有顶点 ,
证明
(在顶点 k 处拆开路径)
考虑从 到 、中间顶点在 内的最小权重简单路径 。若 不是 的中间顶点,则 已计入 。若是,由于 简单, 恰好出现一次;在 处切开,得到 与 两条简单路径,中间顶点都在 内,由最优子结构其权重分别为 与 。反过来,两个表达式各自都是一条中间顶点在 内的真实途径的权重;又因无负圈,这类最小权重途径可取为简单的(删去圈不会增加权重)。故两式之最小值恰为 。
当 时,。
D = D0
for k = 1..n:
for i = 1..n:
for j = 1..n:
if D[i][k] + D[k][j] < D[i][j]:
D[i][j] = D[i][k] + D[k][j]
一个矩阵已经足够。第 轮中第 行与第 列不会改变: 只有在 ,即 时才会改变,而无负圈时 。所以就地读取的值与读取 的结果相同。时间为 ,空间为 ,与 无关。对无负圈的稠密图,这与从每个源点各跑一次 Dijkstra 相当;有负权时,它是简单的选择。
概念视角代数
把全点对距离看成最小加矩阵的幂
定义 。因为 的对角线为零, 就是从 到 、至多 条边的路径中的最小权重。在没有负圈时,最短路径可取为简单路径,所以 。Floyd–Warshall 则通过逐个加入中间顶点,得到同一个矩阵。
若存在负圈,标准结论是某个对角元 会变为负数,这是常用的检测方法;但此时矩阵中的其他数值可能不可靠,所以对角线出现负数即表示“停止,经过该圈的距离没有定义”。
6. 例题:含负边的 Floyd–Warshall
例题 16.3.8
(含负边的 Floyd–Warshall)
顶点 ,边为 (3)、(8)、(−2)、(6)、(1)、(5)。穿过全部四个顶点的圈 权重为 ;其余的圈( 为 14, 为 14)也为正,故假设成立。以下各行为 。
:第 1 行 ;第 2 行 ;第 3 行 ;第 4 行 。
:只有 的 有限。,。第 4 行 。
:第 2 列在 有限,值为 ;第 2 行为 。,,, 维持 0。
:第 3 列对 为 ;第 3 行为 。,, 维持 0。
:第 4 列为 ;第 4 行为 。第 1 行:,,。第 2 行:,,。第 3 行:,,。
最终矩阵:第 1 行 ;第 2 行 ;第 3 行 ;第 4 行 。验算 :从 3 出发唯一的出路是 ,权重 。
例题 16.3.9
(负圈出现在对角线上)
顶点 ,边 (1)、(−3),圈的权重为 。。 时 。对角线上的负数揭示了负圈。
7. 常见错误
常见错误
(有负边但没有负圈)
Dijkstra 的假设是每条边都满足 ,并不只是没有负圈。无圈图 (2)、(3)、(−2)根本没有圈,但 Dijkstra 输出 ,而 。应改用 Bellman–Ford;全点对情形则用 Floyd–Warshall。
常见错误
(顶点一被发现就视为已确定)
标签只有在其条目以当前最小键被取出时才是最终的,顶点刚被到达时并不是:较后确定的顶点可能提供更轻的路线。在第一个例题中, 最初得到标签 ,最终却是 。
常见错误
(关于 k 的循环必须在最外层)
Floyd–Warshall 的不变量针对允许的中间顶点集合 ,所以必须先对所有顶点对 完成第 轮更新,才可纳入 。若把 放在最内层,某个顶点对在后面的中间顶点尚未组合之前就已结束,需要多个中间顶点的路径便可能被漏掉。
还有三个须留意的疏忽:
- 没有跳过过时的堆条目,造成多余的工作并扭曲运算次数。
- 以有限的哨兵值代表 时计算 :应先确认两个操作数都是有限值。
- 输入可能含负圈时,没有检查对角线是否有负元素就把 Floyd–Warshall 的矩阵当作有效结果。
练习
快速检查
(在边 (2)、(5)、(1)、(7)、(2)上,从 执行 Dijkstra。写出确定次序与最终距离。)
每次改进都会产生新的堆条目,旧条目随即过时。
解答 · 答案
取出 :、。取出 : 改进为 ,。取出 : 改进为 。其后 为过时条目;取出 时确定 , 为过时条目。确定次序为 。距离:、、、(路径 )。
快速检查
(边:(1)、(4)、(−5)。Dijkstra 对 输出什么? 又是多少?)
看看 被确定时,边 会怎样。
解答 · 答案
Dijkstra 先确定 (、),再确定标签为 1 的 (没有出边),然后确定标签为 4 的 。边 因 已确定而被忽略,输出为 。但途径 的权重为 ,故 ,Dijkstra 在此给出错误答案。
快速检查
(某图有 个顶点而没有任何边。从 出发的 Dijkstra 会向堆插入什么?输出是什么?)
数一数究竟可能发生多少次松弛。
解答 · 答案
只会插入初始条目 。它被取出并确定 ;没有边可松弛,堆随即变空。输出为 ,其余顶点 ,这是正确的,因为其他顶点都不可达。这正是插入数上界 在 时的情形。
练习 16.3.10
(在顶点 、边 (4)、(5)、(−1)、(2)上执行 Floyd–Warshall,写出最终矩阵。)
核心
解答(3)
- 1
写出初始矩阵
:第 1 行 ,第 2 行 ,第 3 行 。(圈 的权重为 。)
- 2
第 与 轮
:只有第 3 行的 有限:,。第 3 行 。
:第 2 列为 ;第 2 行为 。;。
- 3
第 轮与答案
:第 3 列为 ;第 3 行为 。,;,。
最终:第 1 行 ,第 2 行 ,第 3 行 。验算:,经 。