algorithm - 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次，每次循环迭代，更新顶点(v)的优先级d(v)需要O(logV)时间在优先队列 PQ 中。但是这个操作需要我们在Priority Queue PQ中寻找顶点(v)，需要O(v)的时间。那么时间复杂度O(E logV)如何。

--编辑-- 如果实际上 while 循环执行了 V 次，每次从 PQ 中提取一个元素，这意味着运行时间是 O(V logV)，对吗？

Answer 1

您不需要在优先级队列中搜索v。当您插入优先级队列时，您可以在一个由 v 索引的数组中保留对插入节点的引用，并立即查找它。