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索引的数组中保留对插入节点的引用，并立即查找它。