为什么Dijkstra算法中的decreasekey需要O(logN)时间？

Question

对于更新部分，

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)，其中key是dist[ID]。如果是这样，在优先级队列中查找 ID 为 w 的节点应该花费 O(N) 时间，而不是 O(logN) 时间。那么，为什么Dijkstra算法中的decreasekey需要O(logN)时间呢？

Answer 1

Dijktra 使用的堆实现与传统的优先级队列实现不同，因此内置的优先级队列库对您没有帮助。唯一的解决方案是实现堆并跟踪数组中堆中每个顶点的位置。当您向堆中插入或删除时，需要更新指向顶点的指针。当您必须在堆中执行decreaseKey 操作时，您将获得堆中顶点的直接位置，并且可以更新该位置处的 Key 值。使用 Heapify 对堆重新排序（需要 O(log n)）。