Time Complexity of Dijkstra Algorithm

Question

I have seen in a lot of articles and here also that the time complexity of dijkstra is O(V + ElogV) But shouldn't the time complexity be O(V + ElogE)?

here is my explanation

Set all nodes distance to infinity and source distance to 0 -> O(V) time
Add source node to priority queue

//priority queue will have a maximum of |E| elements and popping or inserting from priority queue                                                                                          
//is done in O(Log|E|) time. So the total complexity for the while loop is O(ElogE)

while the priority queue is not empty:
    pop min from the priority queue -> O(logE) time
    if the popped element is visited:
         continue
    else mark the popped element as visited
    for all edges from popped node (u, v, w):
         if dist[v] > dist[u] + w:
              dist[v] = dist[u] + w
              add (v, w) to the priority queue -> O(logE)

So shouldn't the time complexity be O(V) + O(ElogE) = O(V + ElogE)?

Answer 1

Your mistake is assuming the runtime of ExtractMin() (or pop min as you called it) is O(log E) - but this one runs in O(log V).

• ExtractMin with runtime O(log V) is called |V| times.
• For creating a Min-Heap, you need time O(V).
• Each Decrease-Operation takes O(log V) time and there are =<|E| of those operations.

So runtime complexity is O((V+E) log V) which is O(E log V) (plus the time you need for initialization, so overall O(V + E log V)).

A more detailed analysis can be found in CLRS, chapter 24.3.

Answer 2

I believe that depends on your implementation. Looking at your pseudocode looks like you perform heappush() resulting in duplicate nodes with different distance values as opposed to implementations that perform a decrease operation i.e. they update the distance of node within the heap so the log(V) actually becomes log(E).