代价为 7 的直达道路可能不如代价分别为 2 和 1 的两段道路。BFS 计算边数,因此一般不能选出加权图中最便宜的路线。Dijkstra 算法记录目前发现的最便宜路线代价,并总是确定当前暂定代价最小的顶点。
本课在现有的 Dijkstra 单元上补充快照堆实现、详细追踪和附解答的短练习。
1. 约定与实现
设 为有限有向图,源点 ,所有边权均为非负实数。允许零权边。无向边可表示为两个有向邻接条目,平行边分别计作独立条目。目标是求从 到每个顶点的最小边权和;不可达顶点的距离为 。
定义
(暂定标号、松弛与已确定顶点)
有限的暂定 dist[v] 是一条已发现途径的代价,因此是真实最短距离的上界。沿边 的一次成功松弛,在 dist[u] + weight(u,v) 严格更小时替换 dist[v],并在严格改进时记录 pred[v]=u。顶点以当前键值从堆中被取出时即已确定,此后它的标号不再改变。
以下实现使用不可变 (distance, vertex) 快照构成的最小堆。相同键值按字母顺序打破平局,只为使追踪可复现;正确性不依赖此规则。
对 v in V:dist[v] = infinity;pred[v] = none;settled[v] = false
dist[s] = 0;heap = [(0,s)]
当 heap 非空:
(k,u) = extract_min(heap)
如果 settled[u] 或 k != dist[u]:继续下一次循环
settled[u] = true
对每条从 u 出发的边 (u,v,w):
如果 not settled[v] 且 k+w < dist[v]:
dist[v] = k+w;pred[v] = u
insert(heap, (dist[v],v))
返回 dist, pred
后续改进不会改变堆中的旧快照。旧数对被取出时,过期或已确定检查会阻止再次扫描出边。按本规则,相等的候选距离不会替换前驱。每个有限标号都来自实际发现的途径;无穷大是数学哨兵,实现时须安全处理,避免不安全算术。
2. 为什么最小当前标号可以安全确定
定理
(Dijkstra 算法的正确性)
设所有边权均为非负。当顶点 以键值 被确定时,,即从 到 的真实距离。因此算法停止时,对每个可达顶点 ,dist[v] 等于 ;对每个不可达顶点,dist[v] 为无穷大。
证明
(按确定顺序归纳)
假设此前所有已确定标号都是真实最短距离。设下一次确定的顶点为 ,当前键值为 。已发现路线给出 。假设 。取一条到 的最短路径,令 为其上第一个尚未确定的顶点,其前驱 已确定。非负权保证该路径到 的前缀代价不超过 ;该前缀本身也是到 的最短路径。确定 时,松弛使 dist[x] 至多等于该前缀代价,而有限暂定标号不能低于真实最短距离。因此 dist[x] = delta(x) <= delta(u) < k。
若 ,这与当前条目检查 k == dist[u] 矛盾。否则 有一个当前堆快照:当前快照若此前已被取出,就会确定 。它的较小键值应先于 被取出,与最小堆规则矛盾。故 。源点从零开始,归纳完成证明。比较前缀与完整路线时用到了非负权;这一贪心论证不能不加修改地用于负边。
证明透视
确定证明中每个假设在哪一步使用
证明是在第一次错误确定处导出矛盾,每个假设都在可指认的一步中使用。归纳假设(此前每个已确定的标号都精确)使 的已确定前驱 精确,所以松弛 后,dist[x] 至多等于前缀代价。非负权只用在一个不等式 :到 的最短路径的前缀不可能比整条路径更贵。若最后一条边为负,这一环节失效,定理也随之失效。有限标号不会低于真实距离,这使 dist[x] 由上界变为精确值 。堆序最后才用到: 的当前快照键值小于 ,所以会先于 被取出,与 的选取矛盾。 的情形由检查 k == dist[u] 排除。论证之所以收尾,是因为 不可能,所以每次确定都精确;归纳会结束,因为每个顶点至多被确定一次。
命题
(前驱链)
算法停止后,对每个可达的非源点顶点 ,顶点 pred[v] 在 之前被确定;从 沿前驱指针追踪,会在有限步内到达 ,反转该序列就是由 到 的一条最短路径。有零权边时同样成立。
证明
(前驱在确定时间上指向过去)
严格改进时记录的前驱,总是从尚未确定的顶点指向设置该指针时已确定的顶点。沿最终前驱指针反向追踪,会在确定时间上不断倒退,因此即使有零权边也不可能成环。此外,pred[v]=u 最后一次设置时,dist[v]=dist[u]+weight(u,v) 成立,而 dist[u] 当时已是最终值,所以沿链各边权相加得 dist[v],由定理它等于 。对可达的非源点目标,沿前驱追踪到 并反转序列。若 dist[target] 为无穷大,则报告没有路线。只保留一个前驱会给出一条最短路线,不一定给出所有并列路线。
3. 例题追踪
例题
(含过期快照的追踪)
取边 (7)、(2)、(1)、(6)、(1)、(8)、(3)。堆键相等时按字母排序。表格记录扫描每个已确定顶点之后当前的有限距离。
| 已确定 | |||||
|---|---|---|---|---|---|
| 0 | 7 | 2 | |||
| 0 | 3 | 2 | 8 | ||
| 0 | 3 | 2 | 4 | 11 | |
| 0 | 3 | 2 | 4 | 7 | |
| 0 | 3 | 2 | 4 | 7 |
旧数对 在 之前被移除并跳过,因为 已确定;旧的 和 稍后也被跳过。 的前驱链为 。反转得到 ,代价为 。
概念视角几何
已确定顶点构成不断扩大的球
设想一团火从 出发,越过每条边所需的时间等于边权,于是 在时刻 着火。被取出的键不会减小,而且对每个半径 ,键不超过 的已确定顶点,恰好构成球 。在追踪例子中,半径 的球含 (),半径 时再加入 。暂定标号是球外紧邻顶点的预测着火时刻,沿离开球的边得出。非负边权使时间向前流动:负边会让顶点比它的来源更早着火。
例题
(零权边与过期快照)
取边 (0)、(0)、(5)和 (0)。确定 :发现 (pred[a]=s)和 (pred[b]=s)。确定 :边 给出 ,是严格改进,所以 、pred[b]=a,并插入新数对 。确定 :发现 ,pred[t]=b。确定 。旧数对 最后被取出并跳过,因为 已确定。所有距离都是 0,前驱链 就是代价为 0 的路线 。
例题
(不可达顶点与指向源点的边)
取边 (4)、(1)和 (2);顶点 不能从 到达。确定 ,发现 ,pred[a]=s。确定 :边 指向已确定的源点,被跳过,因为已确定的顶点不再被松弛。堆已空,运行结束,、、,pred[c]=none。边 从未被扫描,因为 从未被确定。
常见错误
(把暂定标号当作距离)
在追踪中扫描 之后,dist[a]=7,但从 到 的距离是 3。暂定标号是已找到路线的代价,在顶点被确定之前只是上界。
常见错误
(扫描过期数对的出边)
若省去检查 settled[u] or k != dist[u],旧数对 会第二次扫描 的出边。标号不会因此改进,因为它的键值不小于精确标号,所以输出不变;但代价会变:一个顶点可能被扫描多次,每个快照一次,“每个邻接条目只扫描一次”的界便失效,下面的时间界也随之失效。
4. 代价与停止条件
命题
(快照堆的运行时间)
使用邻接表、精确的常数时间算术及二叉最小堆时,算法的运行时间为 ,不计图本身的存储,辅助空间为 。
证明
(计算扫描、插入与堆操作的次数)
假设使用邻接表、精确的常数时间算术及二叉最小堆。初始化数组耗时 。每个顶点只确定一次,每个出边邻接条目最多扫描一次。成功松弛至多 次,因此插入的快照至多 个。堆操作耗时 。总时间为 ,包括不连通和无边情形。不计图存储,数组与堆使用 辅助空间。
具有 decrease-key 的索引堆有不同的空间与操作次数,不能悄悄把一种实现的界套到另一种上。
如果只需要一个目标的距离,在其当前条目被取出并确定时停止是正确的。首次发现时停止则不正确:更便宜的路线可能稍后到达。提前停止不能计算其他所有距离;若在扫描目标的出边之前停止,仍可达的顶点可能尚未被发现。
反例模式
目标的首个有限标号不是它的距离
断言:目标 一得到有限标号,搜索就可以停止。在上面的追踪中, 在 被确定时首次得到标号:边 给出 ,pred[t]=a。此时停止会报告路线 ,代价 。但稍后确定 会把 改进为 ,真实距离是 7,路线为 。修正办法是只在 的当前数对被取出并确定时才停止;在这个追踪中就是数对 。
5. 即时检查
快速检查
(对边 (4)、(1)、(2)和 (1)运行算法。给出到 的距离及其前驱链。)
解答 · 答案
处理 后,标号为 、。确定 ,把 改进为 3。确定 ,发现 。然后确定 。到 的距离为 4,前驱链为 ,路线 的代价为 。
快速检查
(在例题追踪中,一共插入多少个快照?其中有多少个在取出时已过期?)
解答 · 答案
先插入源点数对 ,而 7 条边每条都产生一次成功松弛,所以共插入 个快照。其中五个用于确定 。另外三个 、 和 已过期,被跳过。
快速检查
(在例题追踪中,pred[a] 被赋值几次?为什么之后不再改变?)
解答 · 答案
两次:扫描 时 pred[a]=s(标号 7),扫描 时 pred[a]=b(标号 3,严格改进)。 被确定之后,没有任何松弛再以它为目标,所以它的前驱已是最终的。