两题都使用有限有向图和非负权重,应用教学正文中的快照堆与严格改进规则。
复习路线。 通过确定过程追踪暂定距离和平局规则。区分目标确定时已知什么,以及完整运行后已知什么。重建路径时,检查相等距离的更新如何影响前驱。
检查清单。 允许零权。过期快照不是一次新的确定。严格更早的确定时间为前驱链接定向。目标处提前停止只保证目标,不保证其他所有距离。
1. 相等标号与提前停止
例题
(相等标号与提前停止)
边为 (2)、(2)、(2)、(2)、(2)、(8)、(8)和 (1)。顶点 孤立。堆键相等时按字母排序,按列出顺序处理各顶点的出边。给出确定顺序、所有最终距离及到 的一条前驱路线。如果确定 后立即停止,且不扫描其出边,哪个可达顶点仍未被发现?
解答。 确定 ,发现 。先确定 ;它发现 。确定 时给两者提供相同代价,严格改进规则不改变它们的前驱。确定 ,将 改进为 6;确定 ,再发现并确定 。 保持无穷大。因此确定顺序为 ;距离为 。一条路线为 ,代价 6;经过 的另一条路线也最短。如果确定 后不扫描其出边就立即停止, 尽管可达仍未被发现;已确定的目标距离 6 仍然正确。
例题
(目标的首次发现与确定)
边为 (10)、(2)和 (3)。扫描 时发现 ,标号为 10,pred[t]=s;同时发现 ,标号为 2。若在首次发现 时停止,会报告代价 10 的路线 。改为确定 :边 给出 ,是严格改进,所以 、pred[t]=a。现在确定 并停止:目标以距离 5 得到保证,路线为 。旧数对 不再起作用,因为数对 会先被取出。
例题
(不同的平局规则改变路线,但不改变距离)
使用第一个例题的图,但堆键相等时改为 先于 。确定 :。先确定 :发现 (pred[c]=b)和 (pred[t]=b)。确定 :它的边给出 和 ,都与当前标号相等,所以没有变化。确定 : 改进为 6,pred[t]=c。确定 ,然后 。距离与之前完全相同,但记录的路线是 ,而不是 。两者代价都是 6;平局规则决定存储哪一条最短路线。
概念视角结构
最短路线就是紧边构成的路径
当最终距离满足 时,称权为 的边 为紧边。每条最短路线都只用紧边,因为它的每个前段本身也是最短的;而由 到 只用紧边的路线,费用必为 ,因为各项逐项相消。所以到 的最短简单路线,恰是紧边子图中由 到 的简单路径。在第一个例题中,紧边是 、、、、 和 ,由此得出上面找到的两条到 的路线; 不是紧边。前驱规则在每个可达顶点上选出一条进入它的紧边,选哪一条则由平局规则决定。
常见错误
(把目标的首次标号当作最终值)
第一次得到有限标号时,该标号是一条已发现路线的代价,不一定最便宜。在含有代价 10 的边 的例题中, 的首个标号是 10,而它的距离是 5。只应在 的当前项目被取出并确定时才停止。
常见错误
(以为提前停止能保证其他顶点)
在 被确定时停止,只能保证 和更早确定的顶点,而不是所有顶点。在第一个例题中,刚确定 就停止, 仍未被发现,而 根本不可达。要得到完整的距离表,必须运行到底。
2. 零权平局与前驱环
反例模式
在平局时更新前驱可能造成环
断言:从已确定的 松弛到已确定的 ,即使只是与当前距离相等,更新 pred[v]=u 也无害。设边为 (1)、(0)、(0)、(1)。确定 ,然后确定 ,此时 pred[a]=s。扫描 发现 ,令 pred[b]=a。确定 时, 给出相等代价 1。该变体赋值 pred[a]=b,于是 pred[a]=b、pred[b]=a;沿前驱会永远交替。距离值却是 。教学算法跳过指向已确定 的边, 则设置 pred[t]=b;路线是 ,代价 2。
修正办法是严格改进规则。该算法只在扫描已确定顶点指向未确定顶点的边、且严格改进时设置前驱。因此前驱的确定时间早于子顶点最终被确定的时间。沿前驱链接追踪时,确定时间严格递减,所以不可能成环。等代价路线可以存在,但这一规则只记录其中一条。
3. 即时检查
快速检查
(对边 (1)、(1)和 (2),在严格改进规则下 pred[t] 是什么?)
解答 · 答案
扫描 时 得到标号 2,pred[t]=s。之后边 给出 ,与标号相等,不是严格改进,所以 pred[t] 仍是 。记录的路线是 ; 与它并列。
快速检查
(在第一个例题中,若刚确定 就停止,哪些顶点的最终距离已得到保证?)
解答 · 答案
已确定的顶点 的最终距离分别为 。 尚未被发现, 不可达,所以这次部分运行对两者都没有保证的值。
快速检查
(对边 (1)、(0)、(0)、(1),每个顶点各被确定几次?)
解答 · 答案
各恰好一次。边 指向已确定的顶点 ,被跳过;任何过期的堆数对在取出时都会被丢弃,所以零权环 不会造成重复确定。
来源:Dijkstra 算法。