Dijkstra算法複雜度anaylsis誤解

考慮下面的算法從Cormen書：Dijkstra算法複雜度anaylsis誤解

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

我們的教授告訴我們，如果我們使用二叉堆，在放鬆操作需要O（登錄| V |），因此的第7-8行的循環取O（| E | * log | V |）..（如果我們使用線性隊列，則鬆弛需要O（1））。我一直在谷歌搜索一段時間，只是無法找到一個很好的解釋。當我們使用二進制堆時，爲什麼放鬆操作需要O（log | V |）？想得到一些幫助。謝謝。

來源

2013-04-12 Rouki

似乎缺少一些東西。在Q中插入內容的唯一地方是第3行，並且在那裏只插入圖的一個節點？什麼是餡餅？ – Sebastian

Pie是父母 – Rouki

在放鬆功能可按，在d密鑰值[V]被更新時，我們需要再次保持最小堆因爲它可能違反了平均堆的性質，所以Relax的整個過程都需要O（log v）時間。 min堆保持不變，並準備提取下一個最小值。

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-12 19:22:59 siddstuff

我相信，一旦你放鬆了一個節點，你將不得不將它們放在二進制堆的正確節點中。最糟糕的情況是，如果當前節點具有可怕的距離值並且是二進制堆中的葉節點，並且您剛剛找到了一個到達該節點的非常好的方法，則必須將該節點從堆底部移至頂部保持最小堆屬性。一個節點可能需要移動電平的數量是log（V） - > O（日誌（V））

來源

2013-04-12 19:06:25 Calpis

在我看來，RELAX需要O(1)。由於每個邊緣只被查看一次，因此會生成O(E)。要點是萃取分鐘需要O(log(V))並且使用V次，其佔O(V log(V))。

因此總而言之，Djikstra在O(V log V + E)（見this page）中運行，獨立於使用堆結構（請參閱this post）。

除此之外，只要調用RELAX操作（而不是每次迭代4-8）就運行min-heap會產生大量的時間開銷。

來源

2013-11-21 12:48:01

如果我們維持最小堆，那麼extract-min（Q）將花費O（1）次。 O（log V）只是由於更新和維護最小堆。

來源

2014-09-10 14:12:34 Priya

Dijkstra算法複雜度anaylsis誤解

回答

相關問題