为什么Dijkstra算法使用递减密钥？

发布于 2025-01-05 02:53:02 字数 411 浏览 5 评论 0原文

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)

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

为什么会这样？两种方法有什么区别？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

阳光下的泡沫是彩色的 2025-01-12 02:53:02

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

在将节点及其新优先级重新插入优先级队列的 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是调用减键所需的时间。

那么这对运行时有什么影响呢？这取决于您使用的优先级队列。下面是一个快速表格，显示了不同优先级队列以及不同 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)

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

简而言之，使用递减键加上良好的优先级队列，可以将 Dijkstra 的渐近运行时间降低到超出继续进行入队和出队的情况下所能达到的程度。

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

希望这有帮助！

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.

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.

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.

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)

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.

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.

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.

Hope this helps!

回复收藏 0 原文