Searching through various sources, I have seen contradictory information on the worst case time complexity for the Dijkstra algorithm using binary heap (the graph being represented as adjacency list).
According to wikipedia https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time
With a self-balancing binary search tree or binary heap, the algorithm requires Θ((E+V) logV) time in the worst case
where E – number of edges, V – number of vertices.
I see no reason why it can't be done in O(V + E logV).
In case E >= V, the complexity reduces to O(E logV) anyway. Otherwise, we have O(E) vertices connected to the start vertex (the algorithm will perform one iteration for each of them). On each iteration we select a vertex and remove it from the heap in O(logV) time. We also need O(logV) time for each update of the minimal distance to a connected vertex. The number of these updates is bound by the number of edges E so in total we need O(E logV) for the updates.
In total we need O(V) to initalize distances to each vertex, O(E logV) for removing vertices from the heap and O(E logV) for updating the heap when shortest distance changes. We get final complexity O(V + E logV).
Am I wrong or is wikipedia wrong?
Best Answer
Dijkstra's algorithm only finds vertices that are connected to the source vertex. The number of these is guaranteed to be <= E, since each such vertex requires an edge to connect it. The body of Dijkstra's algorithm therefore requires only O(E log V) time.
The version given on the wikipedia page, however, performs an initialization step that adds each vertex to the priority queue, whether it's connected or not. This takes O(V log V) time, so the total is O((V+E) log V).
You imagine an implementation that only initializes distances, without adding them to the priority queue immediately. That is also possible, and as you say it results in O(V + E log V) time.
Some implementations require only constant time initialization, and can run in O(E log V) total