图均有限且有向。除非题目明确改变假设,边权均非负。使用教学正文中的严格改进前驱规则。
复习路线。 源点从零开始,松弛出边,确定当前标号最小的顶点,并由前驱重建路线。使用证明之前检查每条边的权重符号。
检查清单。 暂定表示已发现,并非最终确定。忽略旧堆快照。这些追踪中相等键值按字母顺序处理。最短路径最小化的是总权重,不是边数。
1. 更便宜的路线稍后到达
例题
(更便宜的路线稍后到达时的确定顺序)
边为 (6)、(1)、(2)、(5)、(2)、(7)、(1)。给出确定顺序、最终距离和到 的一条最短路径,并解释为什么在首次发现时固定 是错误的。
解答。 处理 后标号为 。确定 ,将 改进为 并发现 。确定 ,将 改进为 并发现 。确定 并将 改进为 ;然后确定 。旧快照被跳过。确定顺序为 ,对应距离为 。前驱给出 ,代价 。首次发现时就固定会把 冻结为 6,尽管稍后存在代价 3 的路线。
例题
(零权边与平局)
边为 (0)、(0)、(0)、(2)和 (2)。给出确定顺序、距离和 pred[t]。扫描 后,标号为 (pred[a]=s)和 (pred[t]=s)。确定 :发现 ,pred[b]=a;而 给出 ,与当前标号相等,不是严格改进,所以 pred[t] 仍为 。确定 :边 指向已确定的顶点,被跳过,因此零权环 不会造成前驱环。确定 。确定顺序为 ,距离为 。pred[t] 记录的路线 是最短的; 与它并列。
例题
(无法到达的目标)
边为 (4)、(1)和 (1);顶点 与 不能从 到达。确定 ,发现 ,pred[a]=s。确定 :边 指向已确定的源点,被跳过。此时堆已空,运行结束,、、。由于 dist[t] 为无穷大,答案是没有到 的路线;pred[t] 仍是 none,不沿前驱链追踪。
常见错误
(选择边数最少的路线)
最短路径最小化的是总权重,不是边数。在第一个例题中,路线 有两条边,代价为 ;最短路径 有四条边,代价只有 。广度优先搜索会给出前者。
常见错误
(把暂定标号当作距离)
在第一个例题中,扫描 后 的标号是 6,但它的距离是 3。暂定标号只是已发现路线的代价,在顶点被确定之前,它只是距离的上界。
2. 负边破坏证明
反例模式
负边使最小值确定规则失效
断言:对任何有限边权,确定当前暂定标号最小的顶点都是安全的。考虑 (2)、(5)、()。扫描 后,标号为 ,所以规则先以 2 确定 。稍后 给出代价 的路线 。这是到 的真实距离,因为该图只有这两条到 的路线。已确定的值 2 错误。证明中,到 的前缀代价为 5,大于完整最短路线代价 1;有负的最后一条边时,前缀代价不一定不超过全程代价。修正办法就是那个假设本身:负边不在 Dijkstra 的保证范围内,边权必须非负。
3. 即时检查
快速检查
(对边 (3)、(1)、(1)和 (1),给出确定顺序、到 的距离和一条最短路线。)
解答 · 答案
处理 后,标号为 、。确定 ,把 改进为 。确定 ,发现 。然后确定 。确定顺序为 ,到 的距离为 3,路线为 ,代价 ;路线 的代价是 4。
快速检查
(在第一个例题中, 以距离 3 确定之后,数对 仍留在堆中。它被取出时会怎样?)
解答 · 答案
它在 之后才被取出,因为它的键值 6 较大。此时 已确定,所以这个数对被跳过,不扫描任何边。旧数对 的情况相同。
快速检查
(在第一个例题中,哪条到 的路线边数最少?它的代价是多少?)
解答 · 答案
路线 有两条边,代价为 。最短路径代价为 6,用了四条边,所以边数最少的路线并非最便宜。
来源:Dijkstra 算法。