GATE CS 2005 Q38 — Shortest Paths (Dijkstra, Bellman-Ford)

To find the time complexity of Dijkstra's single-source shortest path algorithm using a binary heap, we analyze the cost of the priority queue operations performed during the algorithm:

1. Initialization: Inserting all $|V|$ vertices into the binary heap takes $O(|V|)$ time.
2. Extract-Min: The algorithm extracts the minimum-distance vertex from the heap exactly once for each vertex. Since there are $|V|$ vertices and each Extract-Min operation on a binary heap of size $O(|V|)$ takes $O(\log |V|)$ time, the total time for all extractions is: $$O(|V| \log |V|)$$
3. Decrease-Key (Relaxation): For each edge processed, we may need to update the shortest path estimate of an adjacent vertex, which corresponds to a Decrease-Key operation in the binary heap. In the worst case, this relaxation happens once for every edge, resulting in at most $|E|$ Decrease-Key operations. Each such operation takes $O(\log |V|)$ time in a binary heap. The total time for all relaxations is: $$O(|E| \log |V|)$$

Summing these components, the total worst-case time complexity is:

Comparison of options:

• Option A: $O(|V|^2)$ is the complexity when using an unsorted array as the priority queue.
• Option B: $O(|E| + |V| \log |V|)$ is the complexity achieved when using a Fibonacci heap.
• Option D: $O((|E| + |V|) \log |V|)$ is the correct complexity when using a binary heap.