优先队列本身不决定键值的意义。Dijkstra 算法按来源出发的暂定路径长度排序;Prim 算法则按生长中树的边界跨越边排序。两者都可用最小堆,但不变量和目标不同。本章以图追踪数据结构,包括过时堆项和父指针。
图与优先队列的表示
无向加权图由顶点及加权边组成。邻接表为每个顶点存储邻点及边权;每条无向边分别出现在两端的表中。最小堆按指定优先值存储项目,并返回最小项,但其底层数组并非排序序列。若平局影响追踪,可指定顶点名称等确定性的次要键;否则可能有多个正确轨迹。
定义 14.2.1
(暂定距离、定案与松弛)
对 Dijkstra,dist[v] 是目前已发现的来源至 路径中的最短长度,尚未必是真正最短距离;父指针记录一条达到此暂定值的路径。起初来源距离为零,其余为无穷大。取出当前暂定距离最小且未定案的顶点,将其定案,再检查其出边。对 的松弛是比较 dist[u]+w(u,v) 与 dist[v];严格改善时替换距离及父节点。本章平局保留原来的父节点。
定义 14.2.2
(惰性堆项与过时项)
堆可支持 decrease-key 以修改既有项。惰性实现则每次严格改善便推入新数对,旧项留在堆内;取出时若顶点已定案或项目的值不等于当前距离,便丢弃。若不检查,过时项可能被误当成新工作。无穷大是概念上的初始标签;实现可以等到发现有限候选值才把顶点入堆。
例题:惰性堆最短路径
例题 14.2.3
(五个顶点上的惰性堆最短路径)
顶点为 A,B,C,D,E,无向边为 AB:2, AC:3, BC:1, BD:3, CD:1, CE:5, DE:2。由 A 出发,堆数对先按距离、再按字母排序;只在严格改善时更新。写出距离、父节点及每次定案后的堆。以下列出的是按优先值排序的堆内容,并非说堆的底层数组已排序。
起初为 [(0,A)]。取出 A 并定案,松弛 A–B、A–C 后堆为 [(2,B),(3,C)],B、C 的父均为 A。取出 B,距离为 2;经 B 到 C 长度为 3,与现值相同,故依平局规则保留父 A。B–D 给出 5;堆为 [(3,C),(5,D)]。
取出距离 3 的 C。C–D 给出 4,将 D 从 5 改善为 4 并把父改为 C;C–E 给出 8。堆变为 [(4,D),(5,D),(8,E)]。取出距离 4 的 D,松弛 D–E,把 E 改善为 6、父改为 D;堆为 [(5,D),(6,E),(8,E)]。弹出 (5,D) 并丢弃:D 已定案,该项过时。取出距离 6 的 E,最后丢弃过时的 (8,E)。
定案距离是 A:0、B:2、C:3、D:4、E:6;父边为 AB, AC, CD, DE。若另一一致规则在相等时替换父节点,C 也可由 B 到达,长度仍为 3。距离和所选最短路径树的身份是不同输出。这棵树的边权和为 8,但 Dijkstra 最小化各顶点的来源路径长度,不是此总和。
常见错误
(没有检查过时就相信弹出的数对)
在追踪中,(5,D) 在 D 已以距离 4 定案之后才被弹出。如果实现把弹出的键值赋给顶点,就会把 dist[D]=4 覆盖成 5;如果再松弛一次 D 的出边,则是以错误的标签重复工作。除非顶点未定案且键值等于当前标签,否则弹出的数对必须丢弃。
概念视角几何
把距离看成火焰到达的时间
把每条边换成长度等于其权的线段,并在时刻 点燃源点。火焰以单位速度蔓延,到达顶点 的时间就是 ,即测地距离;Dijkstra 按火焰到达的次序确定各顶点:最小的暂定标签,就是火焰下一个到达的顶点。在追踪中,火焰在 到达 A,在 到达 B,在 到达 C(沿 AC 或 ABC 都一样),在 到达 D,在 到达 E。负权相当于倒着烧的引线,所以非负条件并非技术细节。
为何可以定案
定理 14.2.4
(取出暂定标签最小的顶点来定案是安全的)
设所有边权均非负,且每个已定案顶点都已带有源点到它的真实最短路径距离。若 是未定案顶点,其暂定标签有限,并且在未定案顶点中最小,则 就是源点到 的真实距离。因此 Dijkstra 算法为每个可达顶点定案时,所用的都是真实距离。
证明
(较短路径会暴露一个标签更小的未定案顶点)
设未定案顶点 的暂定标签最小,却有较短的来源至 路径。沿该路径取第一个未定案顶点 及其已定案前驱 。 定案时已松弛边 ;若已定案的 标签正确, 的暂定标签至多是该路径至 的前缀长度。剩余边权非负,所以前缀不长于整条假定的较短路径;于是 dist[y] 会小于 dist[u],与选择 矛盾;若 ,这立即给出 dist[u] < dist[u]。从来源开始归纳即可。若没有有限的未定案标签,未发现顶点便不可由来源到达。
证明透视
三个假设,各用一次
这些假设按固定顺序出现。归纳假设,即已定案标签是真实距离,给出 路径到 的前缀长度;由于 定案时已松弛边 ,便有 到 的前缀长度。非负边权只用一次,用来由这个前缀过渡到整条假定的较短路径。最后, 的标签最小,使 成为矛盾。
去掉非负假设,只有中间一步会失效。在下面的例子中,前缀 AC 的长度为 5,而整条路径 ACB 的长度只有 1。
非负假设确实重要。
反例模式
负边会破坏定案规则
对有向边 权 2、 权 5、 权 −4,按最小标签定案会先以 2 定案 B,再处理距离 5 的 C;但 长度为 1。图中根本没有有向环,因此失败不是由负环造成。定案后再松弛 B,不能修复一个把定案标签视作最终值的实现;输入有负边时须选用假设允许负边的算法。
Prim 的前沿表示割,而非路径
定义 14.2.5
(Prim 算法的前沿与过时边)
Prim 维持已入树的连通顶点集 。前沿包含一端在 、另一端在外的边;选最小跨割边,加入其外端及该边,再更新前沿。实现可在顶点入 时将边推进堆;取出边后若两端都已在内,便丢弃。这与 Dijkstra 比较距离标签的过时项条件不同。
引理 14.2.6
(安全边引理)
设 是连通无向加权图。设边集 包含于某棵最小生成树 ,并设割 没有被 的边跨越。若 是此割的一条最轻跨割边,则存在一棵最小生成树包含 。
证明
(交换一条跨割边)
若 已在 中,无须交换;否则加入 形成环,环上另有一条跨越同一割的边。因没有 的边跨割,被替换的边不属于 。以 替换它可保留 ,仍是生成树且权重不增加,故所得树亦最小。
证明透视
割的条件如何保护交换步骤
每项假设各用一次。 提供一棵可供修改的最小树。加入 后形成的圈穿过割的次数必为偶数,所以圈上还有另一条跨割边 ;“ 中没有边跨过这个割”这项假设,保证 ,因此删去 后 仍然保留。关键一步是这次交换,而不是重新建一棵树。最后, 最轻给出 ,所以总权不会增加。若允许 跨过割, 就可能属于 ,交换便会把它破坏。
在 Prim 中,已选边都位于 内,故当前割符合此条件;引理在每次选择后保持不变量。允许平局,不同选择可能得到不同最小树。
反例模式
割不能跨过已选的边
声称:若 含于某棵最小生成树,则任何割上最轻的跨割边都能扩充 ;“ 不跨过该割”这个条件是多余的。取边 AB:2, AC:2, BC:1,(含于权为 的最小树 ),以及把 与 分开的割。AB 与 AC 都是最轻的跨割边,而 本身就跨过这个割。选 得到权为 的 ,它不含于任何最小树。若取尊重 的割,例如把 与 分开,最轻的跨割边是 BC,而 是最小树。
例题:在同一图执行 Prim
例题 14.2.7
(在同一图上执行 Prim)
从 A 开始,用边堆;若取出时两端已被选入,便舍弃该边。A 的前沿是 AB:2, AC:3。选 AB 并加入 B;新候选包括 BC:1, BD:3,故选 BC 并加入 C。C 加入跨割候选 CD:1, CE:5(AC 此时两端都已选,是过时项)。选 CD 并加入 D,D 又提供 DE:2。选 DE 并加入 E。所选边是 AB:2, BC:1, CD:1, DE:2,总权重 。
这棵树不同于 Dijkstra 树:它用 BC 而非 AC。由 A 到 C 的树内路径长度为 3,与直边相同;到 E 长度为 6。故本例的最小生成树碰巧也达到该来源的最短距离。Dijkstra 选出的树权重是 8,而 Prim 的树是 6;即使某个最小生成树碰巧也提供最短路径,两者目标仍不同。一般而言最小生成树未必是最短路径树,反之亦然。
常见错误
(最短路径树不是最小生成树)
上面的 Dijkstra 树有边 AB、AC、CD、DE,权重为 8,而最小生成树的权重是 6。从 A 出发的最短距离和最小总权重是不同的目标,一棵树满足其中一个,并不表示它也满足另一个。
追踪在五个顶点全部入树后结束,不需等堆清空。若图不连通,从 A 开始的 Prim 只到达 A 的连通分量;要得到最小生成森林,须对每个余下分量另行开始,或指定另一程序。
例题 14.2.8
(不可达的顶点与孤立顶点)
取顶点 A、B、C、D,边为 AB:4, BC:1;D 没有边。从 A 出发的 Dijkstra 依次定案 A:0、B:4、C:5,永远发现不到 D,它的标签保持无穷大:D 不可达。从 A 出发的 Prim 接受 AB,再接受 BC,总权重为 5,此时堆已清空而 D 仍在树外。改从 D 重新开始,得到一棵没有边的树,所以最小生成森林有两棵树,权重为 5。
成本及检查
邻接表配惰性堆时,每次严格改善推入一项;来源顶点定案时扫描其每个有向邻接项一次。普通二叉堆下,包含初始化的一个保守上界为时间 、空间 。若使用配有适当顶点位置映射的 decrease-key 堆,可得到熟悉的 界。这些界按所述表示法计算比较和堆操作;稠密矩阵表示有不同的扫描成本。
相信追踪前,核实每条父边存在、每个 Dijkstra 标签在定案时等于父标签加边权,且每条报告为可达的路径由来源开始。对 Prim,检查每条接受边跨越当前割、在所有跨割边中权重最小(允许平局),并恰引入一个新顶点;有 条边的连通结果是树。操作计数或小例子都不能证明无条件的平均情况界。优先队列是机制,而不变量决定它容许定案什么。
为何惰性堆仍取出当前最小值
命题 14.2.9
(惰性堆取出的是当前最小值)
在惰性实现中,丢弃过时项之后,第一个被接受的数对是 ,其中 是未定案顶点,其有限的当前标签在未定案顶点中最小。
证明
(堆的一条表示不变量)
惰性实现保持具体表示不变量:每个具有有限 dist[v] 且未定案的顶点,堆内至少有一项 (dist[v],v)。初始来源项建立此性质;每次严格松弛改变标签时都推入新项,因此保持此性质。旧项可留在堆内,但标签不会增加。弹出时只有当键值仍等于当前标签且顶点未定案,才接受该项。若有更小有限标签的未定案顶点,其当前数对必在堆中,便不可能先取出较大的键。故丢弃过时项后,接受项的标签是当前最小值。堆不变量本身只保证最小的已存储数对;当前项和过时项规则把这事实连接到抽象 Dijkstra 不变量。
命题 14.2.10
(惰性 Dijkstra 的成本)
使用邻接表及二叉堆时,惰性实现至多推入 个数对,时间为 ,空间为 。
证明
(计算推入与弹出的次数)
使用邻接表,每个定案顶点的表只扫描一次。每次成功严格松弛至多产生一次新入堆;无向图扫描的有向邻接项至多 ,故推入至多 项,每项至多弹出一次。二叉堆包含初始化的时间为 ,包含邻接表的空间为 。这是所述惰性表示法的最坏计数,不是期望哈希界。简单图满足 ,故 ;替换对数须使用此关系,不能对任意平行边作未声明假设。decrease-key 堆存储的状态及操作次数不同。
森林与负边权的角色
若 Prim 的边堆清空时仍有顶点不在 ,便没有边把 连至余下顶点,表示该连通分量已完成。选另一个未访问顶点,以空前沿重新开始;重复后每个分量各有一棵最小生成树,孤立顶点则是没有边的树。其并集是最小生成森林:生成森林不能使用不同连通分量之间的边,而若某个分量可换成更轻的树,总权重便会下降。
负边权不会破坏 Prim 的割论证;它比较跨割边权并交换边,两步都不假设非负。例如两个顶点只由权重 的边连接,其唯一生成树就是该边。这与最短路径不同:若把无向边解作两条有向弧,沿负边来回会形成负权闭游走,最短游走问题可能没有有限最小值。不可把 Dijkstra 的非负条件机械地套给最小生成树,也不可把割证明套到最短路径。
练习与详解
快速检查
(以“遇到相等距离就替换父节点”的规则重演惰性堆的追踪。哪个父节点会改变?所得树的权重是多少?)
留意 B 定案的一刻。
解答 · 答案
只有 C 的父节点改变。B 定案时,路径 A、B、C 的长度为 3,与当前标签相等,所以在新规则下 C 的父节点变成 B。所有距离都没有改变。树的边是 AB、BC、CD、DE,总权重为 ,与 Prim 得到的是同一棵树。
快速检查
(在同一图上从 C 开始执行 Prim,平局时按新顶点的字母顺序决定。依次接受哪些边?总权重是多少?)
留意哪些前沿边会变成过时项。
解答 · 答案
由 出发,最轻的跨割边是 CB:1 与 CD:1,平局时取 B。接着接受 CD:1。然后 BA:2 与 DE:2 同为权重 2;因为 A 排在 E 之前,先接受 BA,再接受 DE。接受顺序是 CB、CD、BA、DE,总权重为 。顺序与从 A 开始的执行不同,但总权重与起点无关。
快速检查
(在第一个追踪中,共推入多少个数对?弹出的数对中有多少个因过时而被丢弃?把推入次数与界 比较。)
按顺序列出所有推入的数对。
解答 · 答案
推入的数对依次是 、、、、、、,共七个。七个都被弹出,其中恰有两个因过时而丢弃: 与 。图有 条边,界为 ,实际次数符合此界。