Dijkstra's Algorithm: Why PQ and Not Q, Intuition, and Time Complexity Derivation

1. Introduction and Core Questions

When studying Dijkstra's shortest path algorithm using a Min-Heap Priority Queue, several foundational questions naturally arise regarding performance, data structure choices, and efficiency:

• Why do we use a Priority Queue (PQ) or a Set instead of a standard FIFO Queue ($Q$)?
• What is the exact intuition behind how Dijkstra's algorithm selects paths greedily?
• How is the $O(E \log V)$ time complexity rigorously derived, even in the worst-case scenario on a dense graph?

2. The Problem with a Standard FIFO Queue ($Q$)

To understand why a standard Queue is inefficient, let us examine what happens when we replace a Min-Heap Priority Queue with a basic FIFO Queue combined with a distance array.

Real-Life Analogy: Exploring Every Road vs. Taking the Shortest Route First

Imagine navigating a road network. A standard FIFO Queue acts like an exhaustive explorer who blindly walks down every single possible route in the order they discover them, regardless of distance. Conversely, a Priority Queue acts like an intelligent GPS that constantly queries: "Out of all the routes I currently know about, which one is the absolute shortest?" and explores that one first.

Step-by-Step Trace Using a Standard Queue ($Q$)

Consider a graph where source node is 0 and all other nodes are initialized to infinity distance ($\infty$).

• Initialization: Push (distance: 0, node: 0) into the Queue $Q$.
• Step 1: Pop (0, 0). Node 0 can reach Node 1 (weight 3, total 3) and Node 2 (weight 1, total 1).
  • Queue updates: [ (3, 1), (1, 2) ]
• Step 2: Pop the next element from $Q$, which is (3, 1) (since it's a FIFO queue, not sorted by weight!).
  • Node 1 reaches Node 3 with a weight of 4, making total distance 3 + 4 = 7.
  • Queue updates: [ (1, 2), (7, 3) ]
• Step 3: Pop (1, 2). Node 2 reaches Node 3 with weight 2, making total distance 1 + 2 = 3.
  • Queue updates: [ (7, 3), (3, 3) ]

Observation of Inefficiency

Notice that Node 3 now has two entries in our standard Queue:

1. (7, 3) discovered via path 0 -> 1 -> 3 (total distance 7)
2. (3, 3) discovered via path 0 -> 2 -> 3 (total distance 3)

Because a standard Queue does not prioritize minimum weights, we end up processing suboptimal, longer paths (7, 3) before or alongside optimal paths. This leads to redundant path explorations, redundant iterations, and an explosion in the number of states processed.

3. Why Greedy Priority Queue (Min-Heap) Wins

By employing a Priority Queue (Min-Heap), the data structure automatically bubbles the minimum distance pair to the top.

Key Differences: Queue vs. Priority Queue

4. The Intuition Behind Dijkstra's Greedy Strategy

Dijkstra's algorithm operates on a strictly greedy mental model:

1. Locally Optimal Choices: At any given step, pick the unvisited node with the currently known minimum distance from the source.
2. Safe Relaxation: Update (relax) all adjacent neighbors of this minimum node.
3. Global Optimality: Because edge weights are non-negative, the moment a node is popped from the Min-Heap, its shortest path is permanently locked and finalized. It can never be updated by a shorter path later.

5. Deconstructing the Time Complexity: $O(E \log V)$

To rigorously derive the time complexity, let us examine the core pseudo-code loop of Dijkstra's algorithm using a Priority Queue.

Pseudo-Code Structure

while pq is not empty:
    curr = pq.pop()                # Pop the minimum element
    for neighbor in adj[curr]:     # Iterate over all adjacent edges
        if dist[curr] + weight < dist[neighbor]:
            dist[neighbor] = new_dist
            pq.push(new_dist, neighbor)

Breaking Down the Components

Let:

• $V$ = Total number of vertices (nodes)
• $E$ = Total number of edges

The while loop runs at most once for every vertex (and potentially a few extra times for outdated states, bounded linearly relative to vertices). Let's denote the vertex processing outer loop as $V$.

Inside the while loop:

1. Pop Operation: Extracting the minimum element from a Min-Heap of size $S$ takes $O(\log S)$ time.
2. Edge Iteration (any): We iterate through all outgoing edges of the current node. Across the entire execution of the algorithm, the inner loop visits every edge in the graph. Total edge traversals sum up to $E$.
3. Push Operation: Whenever a shorter distance is found, we push the updated pair into the Priority Queue, taking $O(\log S)$ time per push.

6. Worst-Case Dense Graph Analysis

To prove the worst-case bound, consider the densest possible undirected/directed graph (excluding self-loops) where every single node is connected to every other node.

Maximum Edges and Heap Size

• In a fully connected dense graph, each node is connected to $V - 1$ other nodes.
• Total number of edges $E$ in the graph = $V \times (V - 1) \approx V^2$.
• In the worst-case scenario, every time a node is popped, it might find shorter paths to all its neighbors, pushing up to $V - 1$ elements into the Heap repeatedly across all nodes.
• Consequently, the maximum Heap size ($S$) at any given time can scale up to $V^2$ (which equals $E$).

Mathematical Derivation Step-by-Step

Substituting the worst-case heap size $S = V^2$ into our complexity formula:

Using logarithm properties ($\log(V^2) = 2 \log V$):

Since in any connected graph the number of edges $E$ is at least $V - 1$ (and up to $V^2$ in dense graphs), the edge term $E \log V$ dominates over $V \log V$.

Therefore, dropping constant multipliers:

7. Summary and Key Takeaways

• Standard Queue Limitation: A FIFO queue causes brute-force exploration of all possible paths without weight prioritization, resulting in massive redundant state evaluations.
• Priority Queue Power: A Min-Heap ensures that the algorithm behaves greedily, visiting the shortest tentative distances first and locking in optimal paths immediately.
• Greedy Invariant: Non-negative edge weights guarantee that once a node is popped from the Min-Heap, its shortest distance from the source is permanently settled.
• Outer Loop Bound: The main extraction loop runs proportional to the number of vertices ($V$).
• Inner Loop Bound: Edge relaxation iterates across all edges ($E$) in the graph.
• Heap Size Scaling: In the worst-case dense graph, heap size reaches $O(V^2)$, which maps directly to the total edge count $O(E)$.
• Final Time Complexity: Rigorously evaluates to $O(E \log V)$, combining vertex extractions and edge pushes logarithmically scaled by heap capacity.