Dijkstra’s Algorithm (Shortest Path)

Dijkstra’s algorithm is a classic method for finding the shortest path from a starting node to every other node in a weighted graph (with non-negative edge weights).

How It Works

1. Initialization
   • Distance Map: Create an object dist where every node’s distance is set to infinity (∞), except the start node which is set to 0.
   • Priority Queue: Use a priority queue (or min-heap) to store nodes ordered by their current shortest distance.
   • Previous Map: Optionally, maintain a previous map to keep track of the best preceding node for each node (useful for reconstructing the shortest path).
2. Main Loop
   While the priority queue is not empty:
   • Extract Minimum: Remove the node u with the smallest distance from the queue.
   • Relaxation: For each neighbour v of u:
     • Compute an alternative distance:
       alt = dist[u] + weight(u, v)
     • If alt is less than dist[v]:
       • Update dist[v] to alt.
       • Set previous[v] to u.
       • Add or update v in the priority queue with the new distance.
3. Result Extraction
   • After processing, the dist object contains the shortest distances from the start node to every other node.
   • To reconstruct the shortest path from the start node to a target node, backtrack using the previous map.

Example Graph

Consider the following graph:

• Edges:
  • A → B (weight = 1)
  • A → C (weight = 4)
  • B → C (weight = 2)
  • B → D (weight = 5)
  • C → D (weight = 1)

Goal: Find the shortest path from node A to node D.

Step-by-Step Execution

1. Initialization:
   • dist = { A: 0, B: ∞, C: ∞, D: ∞ }
   • previous = {}
   • Priority Queue: [(A, 0)]
2. Processing Node A:
   • Dequeue A (distance = 0).
   • For neighbour B:
     • alt = 0 + 1 = 1 → Update dist[B] = 1, previous[B] = A.
   • For neighbour C:
     • alt = 0 + 4 = 4 → Update dist[C] = 4, previous[C] = A.
   • Queue becomes: [(B, 1), (C, 4)].
3. Processing Node B:
   • Dequeue B (distance = 1).
   • For neighbour C:
     • alt = 1 + 2 = 3 → Update dist[C] = 3, previous[C] = B.
   • For neighbour D:
     • alt = 1 + 5 = 6 → Update dist[D] = 6, previous[D] = B.
   • Queue becomes: [(C, 3), (C, 4), (D, 6)]
     (Duplicates in the queue are handled appropriately in a proper priority queue implementation.)
4. Processing Node C:
   • Dequeue C (distance = 3).
   • For neighbour D:
     • alt = 3 + 1 = 4 → Update dist[D] = 4, previous[D] = C.
   • Queue becomes: [(D, 4), (D, 6)].
5. Processing Node D:
   • Dequeue D (distance = 4).
   • D has no neighbours needing updates.
   • The queue is now empty.
6. Reconstructing the Shortest Path from A to D:
   • Start at D: previous[D] = C
   • Then C: previous[C] = B
   • Then B: previous[B] = A
   • Path: A → B → C → D with a total distance of 4.