对于更新部分,
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)时间呢?
Dijktra 使用的堆实现与传统的优先级队列实现不同,因此内置的优先级队列库对您没有帮助。唯一的解决方案是实现堆并跟踪数组中堆中每个顶点的位置。当您向堆中插入或删除时,需要更新指向顶点的指针。当您必须在堆中执行decreaseKey 操作时,您将获得堆中顶点的直接位置,并且可以更新该位置处的 Key 值。使用 Heapify 对堆重新排序(需要 O(log n))。
您说优先级队列中的减少键需要
O(N)
时间是正确的。因此,要使算法在 O(nlogn)
时间内运行,您有以下两个选项之一:
实现一个优先级队列,您将在其中存储节点的位置。这种类型的优先级队列支持在
O(log n)
时间内删除节点。你可以在here找到一个实现(用java)。以及使用这个 IndexMinPriorityQueue 的 dijkstra 算法代码here.将新值插入优先级队列而不是decreaseKey操作。然而,最坏情况下的空间使用量将增加到
O(M)
,而之前是 O(N)
,其中 M 是边数。您可以验证该算法是否也有效。事实上,这是大多数应用程序中选择的方法,其中图中的边数很少并且可以容纳在内存中。
for(all neighbors w of u){
if (dist[w] > dist[u] + l(u,w)) {
dist[w] = dist[u] + l(u,w);
prev[w] = u;
insert(H,w);
}
}
在堆中,decreaseKey 始终需要 O(logN)。 证明