Dijkstra's Algorithm Step-by-Step Execution
You'll learn: How to manually trace through Dijkstra's algorithm on a graph to see exactly how vertices are processed and distances updated.
The Core Process
Dijkstra's algorithm finds shortest paths by repeatedly picking the "closest unvisited vertex" and updating its neighbors. Let's trace a complete example to see this in action.
Complete Example
Consider a graph with vertices {A, B, C, D} starting from A:
- A connects to B (cost 1) and C (cost 4)
- B connects to C (cost 2) and D (cost 5)
- C connects to D (cost 1)
Execution Trace
Step 0 (Initialization):
- Distances: A=0, B=∞, C=∞, D=∞
- Unvisited: {A, B, C, D}
Step 1: Pick A (smallest distance = 0)
- Relax A→B: distance[B] = min(∞, 0+1) = 1
- Relax A→C: distance[C] = min(∞, 0+4) = 4
- Mark A as visited
Step 2: Pick B (smallest unvisited = 1)
- Relax B→C: distance[C] = min(4, 1+2) = 3 ✓ (improvement!)
- Relax B→D: distance[D] = min(∞, 1+5) = 6
- Mark B as visited
Step 3: Pick C (smallest unvisited = 3)
- Relax C→D: distance[D] = min(6, 3+1) = 4 ✓ (improvement!)
- Mark C as visited
Step 4: Pick D (only unvisited left)
- No outgoing edges
- Done!
Final shortest paths from A: B=1, C=3, D=4
The Pattern
Each iteration processes one vertex permanently. The key insight: once selected, a vertex's distance is final because all shorter paths would have been discovered earlier.
Key Takeaway: Dijkstra's algorithm builds shortest paths incrementally by always choosing the closest unprocessed vertex and relaxing its neighbors, guaranteeing optimal distances when each vertex is finalized.