为什么Dijkstra的algorithm使用减键？
Dijkstra的algorithm教给我的如下
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) 但是我一直在做一些关于algorithm的阅读，我看到很多版本使用减less键而不是插入。
这是为什么，这两种方法有什么区别？
使用减less键而不是重新插入节点的原因是为了使优先级队列中的节点数量保持较小，从而减less了优先级队列出队总数，并使每个优先级队列的成本平衡较低。
在Dijkstraalgorithm的实现中，将节点重新插入具有新优先级的优先级队列中，将一个节点添加到图中每个m边的优先级队列中。 这意味着在优先级队列上有入队操作和出列操作，总运行时间为O（m T e + m T d ），其中T e是入队到优先队列所需的时间，T d是从优先级队列中出列所需的时间。
在支持递减密钥的Dijkstraalgorithm的实现中，保存节点的优先级队列从其中的n个节点开始，并且在algorithm的每个步骤上移除一个节点。 这意味着堆出队的总数是n。 每个节点将有可能一次调用每个边的减less键，所以减less键的总数最多为m。 这给出了（n T e + n T d + m T k ）的运行时间，其中T k是调用减键所需的时间。
那么这对运行时有什么影响？ 这取决于您使用的优先级队列。 下面是一个快速的表格，展示了不同的优先级队列以及不同Dijkstraalgorithm实现的总体运行时间：
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)
正如你所看到的，对于大多数types的优先级队列，渐近运行时确实没有什么区别，而减less键版本不太可能好得多。 但是，如果你使用斐波那契堆优先级队列的实现，那么当使用减键时，Dijkstra的algorithm确实会渐近效率化。
简而言之，如果继续使用排队和出队，使用减键，加上一个优先级队列，可以使Dijkstra的渐近运行时间超出可能的范围。
除此之外，一些更高级的algorithm，如Gabow的最短pathalgorithm，使用Dijkstraalgorithm作为子程序，并且严重依赖于减less密钥的实现。 他们使用这样一个事实，如果您事先知道有效距离的范围，则可以基于该事实构build一个超高效的优先级队列。
希望这可以帮助！
在2007年，有一篇文章研究了使用减键版本和插入版本之间执行时间的差异。 见http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf
他们的基本结论是不使用大多数图的减less键。 特别是对于稀疏图，非减less键比减less键的版本快得多。 请参阅纸张了解更多详情。
