algorithm - 为什么 Dijkstra 的算法使用减少键？

Question

教给我的Dijkstra算法如下

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

但我一直在阅读有关算法的一些资料，我看到的很多版本都使用 decrease-key 而不是 insert。

这是为什么，这两种方法之间有什么区别？

Answer 1

之所以使用 decrease-key 而不是重新插入节点，是为了让优先级队列中的节点数量少，从而使优先级队列出队的总数少，每个优先级队列平衡的成本也低。

在 Dijkstra 算法的实现中，将节点重新插入到具有新优先级的优先级队列中，一个节点被添加到图中 m 条边的每一个的优先级队列中。这意味着优先级队列上有 m 个入队操作和 m 个出队操作，总运行时间为 O(m T_e + m T_d)，其中 T< sub>e 是进入优先级队列所需的时间，T_d 是从优先级队列中出队所需的时间。

在支持递减键的 Dijkstra 算法的实现中，包含节点的优先级队列从其中的 n 个节点开始，并且在算法的每一步中删除一个节点。这意味着堆出列的总数为 n。每个节点将有可能对每条通往它的边调用一次减少键，因此完成的减少键总数最多为 m。这给出了 (n T_e + n T_d + m T_k) 的运行时间，其中 T_k是调用 decrease-key 所需的时间。

那么这对运行时有什么影响呢？这取决于您使用的优先级队列。这是一个快速表格，展示了不同的优先级队列和不同 Dijkstra 算法实现的总体运行时间:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

如您所见，对于大多数类型的优先级队列，渐近运行时确实没有区别，减少键版本也不太可能做得更好。但是，如果您使用 Fibonacci heap优先级队列的实现，那么当使用减少键时，Dijkstra 算法确实会渐进地更有效。

简而言之，使用 decrease-key 加上一个良好的优先级队列，可以降低 Dijkstra 的渐近运行时间，如果您继续进行入队和出队则可能超出此范围。

除此之外，一些更高级的算法，如Gabow的最短路径算法，使用Dijkstra的算法作为子程序，并且严重依赖于减少键的实现。他们利用的事实是，如果您事先知道有效距离的范围，就可以基于该事实构建一个超高效的优先级队列。

希望这对您有所帮助!