I'm having a hard time understanding why the complexity of Dijkstra's Algorithm with a Heap is O( (m + n)*log(n) ) where m is the number of edges and n is the number of vertices.
My understanding is:
Now I know one has to do n remove mins. (Each remove min takes log(n) from a heap).
Then one has to do m update keys. (Each update key takes log(n)).
Hence the answer. Is my concept clear? Otherwise can you please explain how to get the time complexity of the Dijkstra's Algorithm.
The complexity varies slightly depending on the way you implement Dijkstra using heap. For instance I am using the built-in priority queue in c++ and this heap does not support priority update. Thus each time I want to update the priority of a given element I simply push one more element in the heap. This may cause my heap to become of size m(still each insert/pop has a complexity of O(log(m)) which is the same as O(log(n))).
If you use Fibonacci heap you can reduce the complexity of the algorithm.
If you use a regular binary heap your analysis is pretty much correct - you need to push m elements in a heap that supports insert/pop in O(log(n)). You also need to remove the minimum element at least n times.
