[FIXED] Why Dijkstra worst time complexity is worse using priority queue compared without using it?

Issue

I know the sequence of step of Dijkstra algorithm is like these:

• Initialize arr min_distance, put source as 0, and the others as MAX_VALUE
• Pick the min distance that's not in visited set
• Put vertex to the visited set
• Loop through all edges linked to the chosen vertex that's not in visited set
• Update all the min distance
• Keep doing it until we get the destination vertex or no other vertex can be picked

So far I've seen 2 type kind of implementation, one using min heap O(log V) to get the minimum vertex, and the other using simple loop (O(V)).

My question is, if we use min heap, it says the time complexity will be O(E log V), E can be written as V^2. While without it, we can get O(V^2) time complexity. Why does the time complexity seems worse when using min heap?

Solution

Why does the time complexity seems worse when using min heap?

With a plain binary heap, it is worse. But only if the number of edges is that large. That is why on Wikipedia it says:

For sparse graphs, that is, graphs with far fewer than |V|² edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using [...] a priority queue to implement extracting minimum efficiently.

It is possible to also keep the time complexity at O(|V|²) when using a heap that can offer a O(1) decrease-key operation, such as a Fibonacci heap. Again quoting from the same article:

With a self-balancing binary search tree or binary heap, the algorithm requires

    Θ((|E|+|V|)log|V|)

time in the worst case [...]; for connected graphs this time bound can be simplified to Θ(|E|log|V|). The Fibonacci heap improves this to

    Θ(|E|+|V|log|V|)

...which -- when |E| = O(|V|²) -- is Θ(|V|²)

Answered By - trincot

Answer Checked By - Pedro (PHPFixing Volunteer)