2

给定 Cormen 书中的以下算法：

DIJKSTRA(G,w,s)

1. INITIALIZE-SINGLE-SOURCE(G,s)
2. S <-- {0}
3. Q <-- V[G]
4. while (Q != {0})
5.    do u <-- extract-min(Q)
6.    s <-- s U {u}
7.    for each vertex v at Adj(u) 
8.            do RELAX(u,v,w)



RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)
       pie(v) <--- u

我们的教授告诉我们，如果我们使用 Binary Heap，Relax 操作需要 O(log|V|)，因此第 7-8 行的循环需要 O(|E|*log|V|)..（如果我们使用线性队列然后放松需要 O(1))。我已经在谷歌上搜索了一段时间，但找不到一个很好的解释。当我们使用二进制堆时，为什么松弛操作需要 O(log|V|)？很想得到一些帮助。谢谢。

4

4 回答 4

1

我相信一旦你放松一个节点，你将不得不将它们放在二进制堆中的正确节点中。最坏的情况，如果当前节点有一个可怕的距离值并且是你的二进制堆中的一个叶节点，而你刚刚找到了一个非常好的方法来到达那个节点，你必须把那个节点从堆的底部移到顶部保持最小堆属性。节点可能需要移动的级别数是 log(V) -> O(log(V))

于 2013-04-12T19:06:25.333 回答
1

在Relax函数中，d[v]处的键值被更新，我们需要再次维护最小堆，因为它可能违反平均堆的性质，所以整个Relax过程需要O(log v)时间。最小堆被维护，它准备好提取下一个最小值。

RELAX (u,v,w)
if d[v] > d[u] + w(u,v)
    then d[v] <-- d[u] + w(u,v)        //* updation.
       pie(v) <--- u
于 2013-04-12T19:22:59.363 回答
1

在我看来，RELAX 需要O(1). 由于每条边都只查看一次，因此会生成O(E). 关键是 extract-min 需要O(log(V))并使用了 V 次，占O(V log(V)).

所以总而言之，Djikstra 可以运行O(V log V + E)（参见此页面），与使用哪种堆结构无关（参见这篇文章）。

除此之外，在调用 RELAX 操作时运行 min-heap（而不是每次 4-8 迭代一次）会产生巨大的时间开销。

于 2013-11-21T12:48:01.930 回答
1

如果我们维护最小堆，那么 extract-min(Q) 将花费 O(1) 时间。O(log V) 只是由于更新和维护最小堆。

于 2014-09-10T14:12:34.320 回答