Dijkstra's Algorithm Runtime

Question

I know that this might not be a good question, but I was wondering how it's runtime is O(ElogV).

Here's the Algo

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. 

Time complexity is given by O(E logV), as the inner loop runs at most E times, and for each loop iteration, it take O(logV) time to update the priority d(v) of vertex (v) in Priority Queue PQ. But this operation requires us to search for the vertex (v) in Priority Queue PQ, which takes O(v) time. So how is the Time complexity O(E logV).

--Edit-- If fact the while loop is executed V times and each time an element is extracted from PQ, which means that running time is O(V logV), right?

Answer 1

You don't need to search for v in the priority queue. When you insert in the priority queue, you can keep a reference to the inserted node in an array indexed by v, and look it up instantly.