Algorithm Dijkstras Algorithm Complete Guide

Example Scenario:

Suppose we have the following weighted undirected graph:

    (0) -------5------- (3)
     | \             / 
    1   3           2  
     |     \       /
    (1)  1  (2)    (4)
    |     /       \
    4   6         8
    | /           \
    (5) ----------- (6)
         7

Each number in parentheses represents a node, and each number between nodes represents the weight of the edge connecting those nodes.

Goal: Find the shortest path from node (0) to all other nodes.

Step-by-Step Solution:

Step 1: Initialization

• Create a list distance[] where distance[i] will hold the shortest distance from the source node (node 0) to node i. Initialize all distances to infinity (∞), except for the source node, which is set to 0.
• Create a set visited[] to keep track of visited nodes. Initially, this set is empty.
• Create a priority queue priorityQueue to process the nodes based on distance. Insert the source node (0) into the priority queue with distance 0.

distance[] = [0, ∞, ∞, ∞, ∞, ∞, ∞]
visited[]  = []
priorityQueue = {(0, 0)}  // (node, distance)

Step 2: Processing Nodes

We will now repeatedly process nodes from the priority queue until the queue is empty.

Processing Node (0)

• Extract node (0) from the priority queue.
• Mark node (0) as visited.

visited[] = [0]

• For each neighbor of node (0), calculate the distance through node (0) and update the distance if it's shorter than the current known distance.

  • Neighbor (1):

    • Current distance: distance[1] = ∞
    • Distance through node (0): distance[0] + 1 = 0 + 1 = 1
    • Since 1 < ∞, update distance[1] to 1.
    • Insert (1, 1) into the priority queue.

  • Neighbor (2):

    • Current distance: distance[2] = ∞
    • Distance through node (0): distance[0] + 3 = 0 + 3 = 3
    • Since 3 < ∞, update distance[2] to 3.
    • Insert (2, 3) into the priority queue.

  • Neighbor (5):

    • Current distance: distance[5] = ∞
    • Distance through node (0): distance[0] + 4 = 0 + 4 = 4
    • Since 4 < ∞, update distance[5] to 4.
    • Insert (5, 4) into the priority queue.

  Now the distance[] and priorityQueue are:

distance[] = [0, 1, 3, ∞, ∞, 4, ∞]
priorityQueue = {(1, 1), (2, 3), (5, 4)}

Processing Node (1)

• Extract node (1) from the priority queue.
• Mark node (1) as visited.

visited[] = [0, 1]

• For each neighbor of node (1), calculate the distance through node (1) and update the distance if it's shorter than the current known distance.

  • Neighbor (0): Already visited, so ignore.
  • Neighbor (2):
    • Current distance: distance[2] = 3
    • Distance through node (1): distance[1] + 6 = 1 + 6 = 7
    • Since 3 < 7, no update is needed.
  • Neighbor (5):
    • Current distance: distance[5] = 4
    • Distance through node (1): distance[1] + 5 = 1 + 5 = 6
    • Since 6 < 4, update distance[5] to 6.
    • Insert (5, 6) into the priority queue, but we already have a (5, 4) in the queue, so we ignore (5, 6).

  Now the distance[] and priorityQueue are:

distance[] = [0, 1, 3, ∞, ∞, 6, ∞]
priorityQueue = {(2, 3), (5, 4)}

Processing Node (2)

• Extract node (2) from the priority queue.
• Mark node (2) as visited.

visited[] = [0, 1, 2]

• For each neighbor of node (2), calculate the distance through node (2) and update the distance if it's shorter than the current known distance.

  • Neighbor (0): Already visited, so ignore.
  • Neighbor (1): Already visited, so ignore.
  • Neighbor (3):
    • Current distance: distance[3] = ∞
    • Distance through node (2): distance[2] + 2 = 3 + 2 = 5
    • Since 5 < ∞, update distance[3] to 5.
    • Insert (3, 5) into the priority queue.
  • Neighbor (6):
    • Current distance: distance[6] = ∞
    • Distance through node (2): distance[2] + 8 = 3 + 8 = 11
    • Since 11 < ∞, update distance[6] to 11.
    • Insert (6, 11) into the priority queue.

  Now the distance[] and priorityQueue are:

distance[] = [0, 1, 3, 5, ∞, 6, 11]
priorityQueue = {(5, 4), (3, 5), (6, 11)}

Processing Node (5)

• Extract node (5) from the priority queue.
• Mark node (5) as visited.

visited[] = [0, 1, 2, 5]

• For each neighbor of node (5), calculate the distance through node (5) and update the distance if it's shorter than the current known distance.

  • Neighbor (0): Already visited, so ignore.
  • Neighbor (1): Already visited, so ignore.
  • Neighbor (6):
    • Current distance: distance[6] = 11
    • Distance through node (5): distance[5] + 7 = 6 + 7 = 13
    • Since 11 < 13, no update is needed.

  Now the distance[] and priorityQueue are:

distance[] = [0, 1, 3, 5, ∞, 6, 11]
priorityQueue = {(3, 5), (6, 11)}

Processing Node (3)

• Extract node (3) from the priority queue.
• Mark node (3) as visited.

visited[] = [0, 1, 2, 3, 5]

• For each neighbor of node (3), calculate the distance through node (3) and update the distance if it's shorter than the current known distance.

  • Neighbor (0): Already visited, so ignore.
  • Neighbor (4):
    • Current distance: distance[4] = ∞
    • Distance through node (3): distance[3] + 2 = 5 + 2 = 7
    • Since 7 < ∞, update distance[4] to 7.
    • Insert (4, 7) into the priority queue.

  Now the distance[] and priorityQueue are:

distance[] = [0, 1, 3, 5, 7, 6, 11]
priorityQueue = {(6, 11), (4, 7)}

Processing Node (4)

• Extract node (4) from the priority queue.
• Mark node (4) as visited.

visited[] = [0, 1, 2, 3, 5, 4]

• Since node (4) has no unvisited neighbors, we just move to the next node.

Processing Node (6)

• Extract node (6) from the priority queue.
• Mark node (6) as visited.

visited[] = [0, 1, 2, 3, 5, 4, 6]

• Since node (6) has no unvisited neighbors, we are done.

Final Result:

The shortest distances from node (0) to all other nodes are:

distance[] = [0, 1, 3, 5, 7, 6, 11]

So, the shortest paths from node (0) are:

• To node (0): 0
• To node (1): 1 (via path: 0 → 1)
• To node (2): 3 (via path: 0 → 2)
• To node (3): 5 (via path: 0 → 2 → 3)
• To node (4): 7 (via path: 0 → 2 → 3 → 4)
• To node (5): 6 (via path: 0 → 1 → 5)
• To node (6): 11 (via path: 0 → 2 → 6)

Conclusion: