为什么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?

推荐答案

之所以使用减少键而不是重新插入节点是保持节点的数目中的优先级队列小，因此减少的优先队列出队的总数小和每个优先级队列的平衡低的成本。

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

在Dijkstra算法的实现，重新插入节点与它们的新的优先次序的优先级队列，一个节点被添加到每个图中的m条边的优先级队列。这意味着有对优先级队列米排队操作和M队列操作，使邻，总运行时间（M牛逼<子>电子 + M牛逼<子>ð），其中T <子>电子是排队到优先级队列和T <子>ð是从优先级队列中退出所需要的时间。

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。每个节点将具有减少键上调用它潜在地一次为每个边朝向，所以做了减少-键的总数至多为米。这给出了（N t个<子>电子 + N t个<子>ð + M牛逼<子> K ），其中T <子> K 运行时所需的时间来调用减少键

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算法将通过减少的时候渐近更有效率-key。

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屋！