3

对于更新部分，

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 算法中的 reductionkey 需要 O(logN) 时间？

4

3 回答 3

4

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

于 2013-11-14T06:14:41.587 回答
0

您说优先级队列中的减少键需要O(N)时间是正确的。因此，要使算法O(nlogn)及时运行，您有以下两种选择之一：

  1. 实现一个优先级队列，您将在其中存储节点的位置。这种优先级队列支持O(log n)及时删除节点。你可以在这里找到一个实现（在 java 中）。还有使用这个 IndexMinPriorityQueue 的 dijkstra 算法代码。

  2. 将新值插入优先级队列而不是 reduceKey 操作。然而，最坏情况下的空间使用量将增加到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);
    }
}
于 2014-03-26T09:10:01.690 回答
-1

在堆中，reduceKey 总是采用 O(logN)。证明

于 2013-11-14T05:51:20.773 回答