为什么 Dijkstra 算法使用减键? [英] Why does Dijkstra's algorithm use decrease-key?

问题描述

教给我的 Dijkstra 算法如下

Dijkstra's algorithm was taught to me was as follows

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)

但我一直在阅读有关该算法的一些资料，我看到很多版本都使用减少键而不是插入.

But I've been doing some reading regarding the algorithm, and a lot of versions I see use decrease-key as opposed to insert.

这是为什么，这两种方法有什么区别?

Why is this, and what are the differences between the two approaches?

推荐答案

使用decrease-key而不是重新插入节点的原因是为了保持优先队列中的节点数量较少，从而保持优先队列出队的总数小且每个优先级队列平衡的成本低.

The reason for using decrease-key rather than reinserting nodes is to keep the number of nodes in the priority queue small, thus keeping the total number of priority queue dequeues small and the cost of each priority queue balance low.

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

In an implementation of Dijkstra's algorithm that reinserts nodes into the priority queue with their new priorities, one node is added to the priority queue for each of the m edges in the graph. This means that there are m enqueue operations and m dequeue operations on the priority queue, giving a total runtime of O(m T_e + m T_d), where T_e is the time required to enqueue into the priority queue and T_d is the time required to dequeue from the priority queue.

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

In an implementation of Dijkstra's algorithm that supports decrease-key, the priority queue holding the nodes begins with n nodes in it and on each step of the algorithm removes one node. This means that the total number of heap dequeues is n. Each node will have decrease-key called on it potentially once for each edge leading into it, so the total number of decrease-keys done is at most m. This gives a runtime of (n T_e + n T_d + m T_k), where T_k is the time required to call decrease-key.

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

So what effect does this have on the runtime? That depends on what priority queue you use. Here's a quick table that shows off different priority queues and the overall runtimes of the different Dijkstra's algorithm implementations:

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)

如您所见，对于大多数类型的优先级队列，渐近运行时确实没有区别，并且减少键版本不太可能做得更好.但是，如果您使用优先队列的 斐波那契堆 实现，那么 Dijkstra 的算法确实会渐近使用减少键时更有效.

As you can see, with most types of priority queues, there really isn't a difference in the asymptotic runtime, and the decrease-key version isn't likely to do much better. However, if you use a Fibonacci heap implementation of the priority queue, then indeed Dijkstra's algorithm will be asymptotically more efficient when using decrease-key.

简而言之，如果您继续进行入队和出队，使用减少键，加上良好的优先级队列，可以将 Dijkstra 的渐进运行时间降低到超出可能的范围.

In short, using decrease-key, plus a good priority queue, can drop the asymptotic runtime of Dijkstra's beyond what's possible if you keep doing enqueues and dequeues.

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

Besides this point, some more advanced algorithms, such as Gabow's Shortest Paths Algorithm, use Dijkstra's algorithm as a subroutine and rely heavily on the decrease-key implementation. They use the fact that if you know the range of valid distances in advance, you can build a super efficient priority queue based on that fact.

希望这有帮助！

这篇关于为什么 Dijkstra 算法使用减键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！