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

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

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

Answer 1

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

在Dijkstra算法的实现中，该算法将节点以其新优先级重新插入优先级队列，将一个节点添加到图中每个m个边缘的优先级队列中。这意味着在优先级队列上有m个入队操作和m个出列操作，总运行时间为O（m Te + m Td），其中Te是排入优先级队列所需的时间，Td是所需的时间。从优先级队列中出队。

在支持reduce-key的Dijkstra算法的实现中，保存节点的优先级队列以其中的n个节点开始，并且在算法的每个步骤中移除一个节点。这意味着堆出队的总数是n。对于通向它的每个边缘，每个节点都会有一个为其调用的减少键，因此减少键的总数最多为m。这给出了运行时间（n Te + n Td + m Tk），其中Tk是调用减小键所需的时间。

那么这对运行时有什么影响？这取决于您使用的优先级队列。这是一个快速表，显示不同优先级队列和不同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实现，那么在使用reduce-key时，Dijkstra的算法确实会渐进地更有效。

简而言之，使用减少键和优先级优先级队列，可以使Dijkstra的渐近运行时间超出可能的范围，如果你继续进行排队和出队。

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

希望这可以帮助！

Answer 2

2007年，有一篇论文研究了使用reduce-key版本和插入版本之间执行时间的差异。见http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

他们的基本结论是不使用减少键来表示大多数图表。特别是对于稀疏图，非减少键明显快于减少键版本。有关详细信息，请参阅该文章。