Dijkstra算法運行時間

Question

我知道這可能不是一個好問題，但我想知道它的運行時間是O（ElogV）。

這裏的算法中

DIJKSTRA(G,w,s) 
S=null 
PQ=G.V 
while (PQ!=null) 
    u=Extract-Min(PQ) 
    S=S+u \\Add node u to set S(explored vertices) 
    foreach (v in adj(u)) 
     if(d(v) > d(u) + w(u,v)) 
      d(v) = d(u) + w(u,v) \\at this step, we need to update the priority d(v) of vertex (v) in the Priority Queue. 

時間複雜度爲O（E logV）給出的，作爲內環最多E時代運行，併爲每個循環迭代，它需要O（logV）時間更新優先級隊列PQ中頂點（v）的優先級d（v）。但是這個操作要求我們在優先級隊列PQ中搜索頂點（v），這需要O（v）時間。那麼時間複雜度O（E logV）如何？

- 編輯 - 如果事實上while循環執行了V次並且每次從PQ中提取一個元素，這意味着運行時間是O（V logV），對吧？

Answer 1

您不需要在優先級隊列中搜索v。當插入優先級隊列時，您可以在由v索引的數組中保留對插入節點的引用，並立即查找它。