Course contentsShow
← Computer Science
Lesson 969 of 2,87223. Shortest Path AlgorithmsFree lesson

Dijkstra's Algorithm Step-by-Step Execution

Tracing through a complete example to understand how vertices are processed and distances updated.

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.