Time complexity of Dijkstra's algorithm

Question

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?

Answer 1

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

Answer 2

Their code adds all vertices to the queue at first, and goes until the queue becomes empty, thus performing $|V|$ extractions (and $|E|$ updates). Of course, it can be optimized - for example, if we minimal known distance in the queue is $\infty$, we can stop. But without this extra check, algorithm can run longer than $O(|V| + |E|\log |V|)$.

Also, depending on implementation, initialization step can also require $O(|V|\log |V|)$ time - for example, if we use self-balancing tree, each insert operation will require $O(\log|V|)$ time.