Dijkstra计算器

伪代码

Dijkstra 是一个贪心算法，其正确性只依赖一条论断：当前距离最近的未确定结点此后不可能再被改进。优先队列以 O(log V) 提供这个结点。

Dijkstra(图, 源点):
    对每个结点 v: dist[v] = 无穷大
    dist[源点] = 0
    pq = 含 (0, 源点) 的优先队列

    当 pq 非空时:
        (d, u) = pq.取出最小()
        若 d > dist[u]: 跳过        // 过期条目
        对每条边 (u, v, w):
            若 dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                父结点[v] = u
                pq.插入((dist[v], v))

过期条目检查很关键。多数标准库不支持在堆中直接减小键值，因此惯常做法是插入一个重复条目，并忽略任何记录距离已经对不上的条目。这称为惰性删除，也正是队列中条目数可能达到 E 而非 V 的原因。

分步示例演算

从 A 出发在一个贪心选择确实奏效的加权图上运行 Dijkstra，观察已确定结点集合如何增长。

示例图: 无向边 A-B (4)、A-C (2)、C-B (1)、B-D (5) 和 C-D (8)。

1. 初始化. dist = A 0，B 无穷大，C 无穷大，D 无穷大。队列中是 (0, A)。
2. 确定 A 为 0. 松弛 A-B 得到 dist[B] = 4，松弛 A-C 得到 dist[C] = 2。队列中是 (2, C) 和 (4, B)。
3. 确定 C 为 2. C 比 B 更近，因此先被取出。松弛 C-B：2 + 1 = 3，优于已记录的 4，于是 dist[B] = 3，并压入新条目 (3, B)。松弛 C-D：2 + 8 = 10，于是 dist[D] = 10。
4. 确定 B 为 3. 条目 (3, B) 先于过期的 (4, B) 浮出。松弛 B-D：3 + 5 = 8，优于 10，于是 dist[D] = 8。
5. 丢弃过期条目. 旧条目 (4, B) 此时浮出。由于 4 大于 dist[B] 的 3，它被直接丢弃，不再重新处理 B。这就是惰性删除在起作用。
6. 确定 D 为 8. 已无可改进之处，算法结束。

最终距离为 A 0、C 2、B 3、D 8，到 D 的最短路径依次经过 A、C、B、D。注意权重为 4 的直接边 A-B 从未被使用：经由 C 只需 3。另外注意结点是按距离 0、2、3、8 的顺序被确定的，这正是贪心论证所依赖的性质。

复杂度及其来源

时间: O((V + E) log V) · 空间: O(V)

使用二叉堆时，V 个结点各被取出一次，每次 O(log V)；E 条边各可能触发一次插入，每次 O(log V)，合计 O((V + E) log V)。采用惰性删除时堆中最多有 E 个条目，取出为 O(log E)，但由于 E 至多为 V 的平方，log E 至多是 2 log V，界限不变。斐波那契堆把理论界限改进到 O(E + V log V)，因为减小键值变为均摊 O(1)，但其常数因子之大使得二叉堆在实践中通常更快。在稠密图上，直接扫描数组求最小值给出 O(V 的平方)，当 E 接近 V 的平方时反而胜过堆。

何时使用迪杰斯特拉算法，何时不宜

Dijkstra 是加权最短路径的默认选择。用什么取代它，取决于你的图违反了它的哪条假设。

常见陷阱

• 在含负权边的图上使用它. 这是最典型的误用。Dijkstra 在结点离开队列时就将其永久确定；之后才发现的负权边本可以改进它，但它再也不会被重新考虑。结果是悄无声息的错误而非报错，这使得该缺陷极难被察觉。此时应改用 Bellman-Ford。
• 省略过期条目检查. 缺少 `若 d > dist[u]: 跳过` 这道守卫，结点会按队列中的条目数被反复处理。算法仍会终止并给出正确答案，但会做无谓的边松弛，在改进次数很多的图上性能可能严重退化。
• 一看到终点就停止. 在松弛过程中触及终点并不意味着它的距离已经确定。只有当终点从队列中被取出时才算确定。在发现时就中断会给出错误答案；在取出时中断则是正确的，而且是一项真正的优化。
• 把零权边当成问题. 零权重完全没有问题。只有严格为负的权重才会破坏论证，因为贪心证明要求距离沿路径非递减，而零保持了这一性质。
• 为每次查询重建整个图. 一次 Dijkstra 运行给出的是源点到所有结点的距离，而不只是到某一个。若你需要多个源点，那是另一个问题：应考虑 Floyd-Warshall 或 Johnson，而不是不加思索地运行 V 次 Dijkstra。

常见问题

Dijkstra 算法有什么用？

它在边权非负的图中求出从一个源点到其余所有结点的最短路径。它驱动 GPS 与公共交通导航、OSPF 与 IS-IS 等路由协议、网络延迟分析，以及在没有可用启发函数时游戏中的寻路。

Dijkstra 算法的时间复杂度是多少？

使用标准实现的二叉堆时为 O((V + E) log V)。斐波那契堆在理论上可降到 O(E + V log V)，但常数因子通常使二叉堆更快。在稠密图上直接扫描数组给出 O(V 的平方)，当 E 接近 V 的平方时可能胜过堆。

为什么 Dijkstra 算法在负权重下会失败？

因为它在某结点拥有队列中最小临时距离时就将其永久确定，前提假设是此后没有任何路径能更短。负权边违反了这个假设：之后发现的路径可能降低一个已确定的距离。由于 Dijkstra 从不重访已确定的结点，它会在毫无报错的情况下返回错误答案。

Dijkstra 和 A* 有什么区别？

A* 就是 Dijkstra 再加上一个对到特定终点剩余距离的启发式估计。Dijkstra 按到源点的距离扩展结点，会找到通往所有地方的路径；A* 按估计的总代价扩展并朝单一终点前进，探索的结点少得多。当启发函数恒为零时，A* 就完全等同于 Dijkstra。

Dijkstra 算法适用于无向图吗？

适用。一条无向边不过是两条权重相同的有向边，算法无需任何改动即可套用。唯一真正的要求是不存在负权重。