About time complexity of dijkstra's algo

#1

why is the time complexity of this algorithm equal to O(ElogV)?

#2

Hey @Senjuti256
if implementing dijkstra algorithm using priority queue and adjacency list-;
you will get time complexity of O((v+e) log(v)).

when number of edges e is greater than v then we can neglect v , therefore total complexity is
O(e log (v))

#3

Pls can you explain me why the complexity will be so?

#4

Hey @Senjuti256

Initialization : O(|V|)
While loop O(|V|)
Find and remove min distance vertices O(log |V|)
Potentially |E| updates O(log |V|) times
So,
Total time O(|V| log|V| + |E| log|V|) = O(|E| log|V|)

#5

How is O(V logV) coming pls can you explain once more?

#6

For a loop of v nodes u find min of all nodes in each iterationwhich is log V
So from here v logv is coming

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

Where are we finding the minimum node? We are making the distance of the src node as 0 and pushing it to the queue. Then we are finding the shorter distances of its neighbours . Thn how is the vlogv coming?

#9

Here we are doing that

#10

Why will update require ElogV time?

#11

In update what we do is updatate dist value of neighbors of current minima
So basically it means for all vertices(because of while loop) we will
Check their neghbors i.e equal to all edges
So for all edges we update data
And updating data is log v
So hence ElogV