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。
为什么会这样？两种方法有何区别？
使用减少密钥而不是重新插入节点的原因是要使优先级队列中的节点数保持较小，从而使优先级队列出队的总数保持较小，并且每个优先级队列平衡的成本较低。
在Dijkstra算法的实现中，该算法使用新的优先级将节点重新插入到优先级队列中，对于图中的m个边中的每条边，将一个节点添加到优先级队列中。这意味着优先级队列上有m个入队操作和m个出队操作，因此总运行时间为O（m T e + m T d），其中T 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)
如您所见，对于大多数类型的优先级队列，渐近运行时实际上并没有区别，并且减小键版本不太可能做得更好。但是，如果您使用优先级队列的Fibonacci堆实现，那么当使用reduce- key时，确实Dijkstra的算法将渐近地更有效。
简而言之，使用减少键和良好的优先级队列可以使Dijkstra的渐近运行时间超出您继续排队和出队的可能性。
除此之外，还有一些更高级的算法，例如Gabow的最短路径算法，使用Dijkstra的算法作为子例程，并严重依赖于reduce- key的实现。他们使用这样的事实：如果您事先知道有效距离的范围，则可以基于该事实建立一个超高效的优先级队列。
希望这可以帮助！
