对于更新部分,
for all neighbors w of u:
if dist[w] > dist[u] + l(u,w)
dist[w] = dist[u] + l(u,w)
prev[w] = u
decreasekey(H,w)
这里w是节点的ID,我觉得应该是pair(ID,key) which key就是dist[ID]。 如果是这样,在优先级队列中找到 ID 为 w 的节点应该花费 O(N) 时间而不是 O(logN) 时间。 那么,为什么Dijkstra算法中的decreasekey需要O(logN)的时间呢?
最佳答案
用于 Dijktra 的堆实现不同于传统的优先级队列实现,因此优先级队列的内置库无法帮助您。唯一的解决方案是实现堆并跟踪数组中堆中每个顶点的位置。当你插入或删除到堆中时,你需要更新指向顶点的指针。当您必须在堆中执行 decreaseKey 时,您在堆中有顶点的直接位置,您可以在该位置更新 Key 的值。使用 Heapify 对堆重新排序(这需要 O(logn))。
关于algorithm - 为什么 Dijkstra 算法中的 decreasekey 需要 O(logN) 时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19970434/