Dijkstra's Algorithm
Scenario
You are building Google Maps. You have millions of intersections connected by roads of different length and traffic delay.
How do you find the absolute fastest route from home to work without calculating every possible path?
Why it exists
Problem: BFS guarantees the shortest path only in unweighted graphs (fewest edges). In weighted graphs, a path with many cheap edges can cost less than a path with one expensive edge.
Naive approach: Use BFS but re-add nodes to the queue every time a cheaper path is found. This causes exponential path re-evaluations and destroys efficiency.
Better idea: Process nodes in order of cheapest known cost, not fewest edges. Use a Priority Queue (Min-Heap). When a node is popped, its shortest path is mathematically finalized.
Mental model
Imagine flooding a landscape with water from a source point. The water flows along paths, taking time proportional to the edge weights. The first time the water reaches a town, that is the absolute fastest way there.
Dijkstra's algorithm tracks a 'tentative distance' for every node, initializing the source to 0 and all others to infinity. The Priority Queue repeatedly pops the unfinalized node with the smallest known distance. For that node, we 'relax' all its outgoing edges: if dist[current] + weight < dist[neighbor], we update the neighbor's distance and push it into the queue. The crucial invariant: when a node is popped, its distance is final. This relies strictly on non-negative weights.
Repeated decision: Which unfinalized node has the smallest known distance?
Explanation
Dijkstra's algorithm is the foundational single-source shortest path algorithm for graphs with **non-negative** edge weights.
### The Algorithm
1. Initialize `dist` table: `dist[start] = 0`, all others `infinity`.
2. Insert `(0, start)` into a Min-Heap (Priority Queue).
3. While the heap is not empty:
- Pop the node `u` with the smallest distance.
- If `u` is already finalized (popped before), skip it.
- Mark `u` as finalized. Its `dist[u]` is now the true shortest path.
- **Relaxation:** For each neighbor `v` of `u` with edge weight `w`:
- If `dist[u] + w < dist[v]`, update `dist[v] = dist[u] + w`.
- Push `(dist[v], v)` into the heap.
Hand-trace (Nodes A,B,C. A→B:10, A→C:1, C→B:2):
- Init: dist={A:0, B:inf, C:inf}. Heap: [(0,A)]
- Pop A (0). Relax neighbors:
- B: dist 0+10 < inf → dist[B]=10. Push (10,B)
- C: dist 0+1 < inf → dist[C]=1. Push (1,C)
- Heap is [(1,C), (10,B)].
- Pop C (1). Finalize C. Relax neighbors:
- B: dist 1+2 < 10 → dist[B]=3. Push (3,B)
- Heap is [(3,B), (10,B)].
- Pop B (3). Finalize B. No neighbors.
- Pop B (10). Skip (already finalized).
- Done! Shortest paths: A=0, C=1, B=3.
### The Invariant and Negative Weights
The heart of Dijkstra is the invariant: **when a node is popped, its distance is final**. Why? Because we always pop the cheapest known node. Any other path to this node would have to go through some other node currently in the heap, which ALREADY costs more. Adding more edges can only increase the cost... **unless negative weights exist**.
If a graph has negative edge weights, Dijkstra breaks. A seemingly expensive path might suddenly become cheap due to a massive negative edge later on, violating the invariant. (In those cases, Bellman-Ford must be used).
Key points
- Priority Queue: Using a Min-Heap instead of a FIFO queue changes BFS into Dijkstra. It ensures we explore the cheapest paths first. Complexity is O(E log V).
- Relaxation: If `dist[u] + w < dist[v]`, then `dist[v] = dist[u] + w`. We are constantly tightening the upper bound on distances until they settle at the true minimum.
- No Negative Weights: The algorithm's correctness hinges on path costs strictly increasing as they grow. Negative weights destroy the 'popped means final' invariant.
Pattern: Dijkstra's (Min-Heap BFS)
Recognition cues:
- Finding the shortest path or lowest cost.
- The graph has weighted edges.
- All edge weights are non-negative.
Failure signals
- Using Dijkstra on a graph with negative weights (will return incorrect results).
- Using a normal array instead of a Min-Heap (degrades time complexity from O(E log V) to O(V^2)).
Engineering examples
Network Routing Protocols
Routing IP packets across the internet efficiently.
OSPF (Open Shortest Path First) and IS-IS protocols build a map of the network and run Dijkstra's to populate router forwarding tables with the lowest-metric paths.
When not to use
- Unweighted graphs: BFS is O(V+E) and perfectly adequate. Dijkstra adds unnecessary O(log V) heap overhead.
- Graphs with negative weights: Dijkstra's greedy assumption fails. Use Bellman-Ford (O(VE)) instead.
Common mistakes
- Forgetting to track finalized nodes: Because relaxing edges pushes duplicate nodes into the heap with lower costs, you will pop the same node multiple times. You must skip it if it's already finalized.
- Initializing distances to 0 instead of infinity: If distances aren't initialized to infinity, the relaxation condition `dist[u] + w < dist[v]` will never be true.
Glossary
- edge relaxation
- The process of checking if a newly discovered path to a node is cheaper than the currently known path, and updating the cost if it is.
- priority queue
- A data structure (usually a Min-Heap) that always pops the element with the lowest priority/cost first.
Recall questions
- What data structure does Dijkstra use to determine which node to process next?
- What is the fundamental invariant of Dijkstra's algorithm when a node is popped from the priority queue?
- Why does Dijkstra's algorithm fail on graphs with negative edge weights?
Questions & answers
Find the cheapest flight from city A to B given ticket prices.
Run Dijkstra's algorithm from A to B. The edge weights are the ticket prices.
Approach: Classic single-source shortest path on a weighted graph.
Network Delay Time: Given a list of directed edges with travel times, how long will it take for a signal sent from node K to reach all nodes?
Run Dijkstra from K. Find the maximum shortest-path distance among all reachable nodes. If any node is unreachable, return -1.
Approach: Dijkstra + checking the max value in the final distance array.
Interesting facts
- Edsger W. Dijkstra conceived the algorithm in 1956 in 20 minutes while drinking coffee with his fiancée, looking for a problem that could be demonstrated on the ARMAC computer without pencil and paper.
Continue learning
Previous: When BFS Stops Working
Previous: Weighted vs unweighted
Previous: Binary heap
Related: BFS on graphs
Related: When BFS Stops Working
Related: Binary heap