Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a greedy approach.

Algorithm

// Dijkstra's algorithm
1. Assign distance 0 to source, ∞ to all others
2. Add all vertices to unvisited set
3. WHILE unvisited set is not empty:
   a. Select vertex U with smallest tentative distance
   b. Mark U as visited (remove from unvisited)
   c. FOR each unvisited neighbour V of U:
        newDist ← dist[U] + weight(U,V)
        IF newDist < dist[V] THEN
          dist[V] ← newDist
          prev[V] ← U          // Record previous node
        END IF
4. Return dist[] and prev[]

Worked Trace

// Graph (undirected, weighted):
// A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, C-E:10, D-E:2

// Source: A
// Initial: dist={A:0, B:∞, C:∞, D:∞, E:∞}

Step 1: Visit A (dist=0)
   → B: 0+4=4  → update dist[B]=4, prev[B]=A
   → C: 0+2=2  → update dist[C]=2, prev[C]=A
   dist={A:0, B:4, C:2, D:∞, E:∞}

Step 2: Visit C (smallest unvisited dist=2)
   → B: 2+1=3 < 4 → update dist[B]=3, prev[B]=C
   → D: 2+8=10 → update dist[D]=10, prev[D]=C
   → E: 2+10=12 → update dist[E]=12, prev[E]=C
   dist={A:0, B:3, C:2✓, D:10, E:12}

Step 3: Visit B (smallest unvisited dist=3)
   → D: 3+5=8 < 10 → update dist[D]=8, prev[D]=B
   dist={A:0, B:3✓, C:2✓, D:8, E:12}

Step 4: Visit D (smallest unvisited dist=8)
   → E: 8+2=10 < 12 → update dist[E]=10, prev[E]=D
   dist={A:0, B:3✓, C:2✓, D:8✓, E:10}

Step 5: Visit E (dist=10) — done

// Shortest paths from A:
// A→B: 3 (via C) | A→C: 2 | A→D: 8 (via C→B→D) | A→E: 10 (via C→B→D→E)

Priority Queue Optimisation

Using a min-heap (priority queue) to always extract the vertex with smallest distance efficiently, the time complexity is O((V + E) log V) where V = vertices and E = edges.

Limitations

• Does not work with negative edge weights (use Bellman-Ford for that)
• Only finds shortest path from one source

Applications

• GPS navigation (shortest route)
• Network routing protocols (e.g. OSPF)
• Social networks (degrees of separation)
• Games (pathfinding for NPCs)