Dijkstra's Algorithm

1. We start by looking at the edges leaving node "s" and build our priority queue. Here it would be:

   • Leaving node "s" and entering node "a" with the weight 7
   • Leaving node "s" and entering node "b" with the weight 4
   • Leaving node "s" and entering node "c" with the weight 4

   The current priority queue is:

   1. "s" - "b" (4)
   2. "s" - "c" (4)
   3. "s" - "a" (7)
2. We pop the edge with the lowest weight, "s" - "b" (4), and look at the edges leaving node "b" (adding its accumulated distance of 4):

   • Leaving node "b" and entering node "e" with weight 1 (Total: 4 + 1 = 5)
   • Leaving node "b" and entering node "f" with weight 3 (Total: 4 + 3 = 7)
   • Leaving node "b" and entering node "a" with weight 6 (Total: 4 + 6 = 10 - ignore, "s" - "a" is already 7)
   • Leaving node "b" and entering node "c" with weight 8 (Total: 4 + 8 = 12 - ignore, "s" - "c" is already 4)

   The current priority queue is:

   1. "s" - "c" (4)
   2. "b" - "e" (5)
   3. "s" - "a" (7)
   4. "b" - "f" (7)
3. We pop "s" - "c" (4) and look at the edges leaving node "c":

   • Leaving node "c" and entering node "f" with weight 8 (Total: 4 + 8 = 12 - ignore, "b" - "f" is already 7)

   The current priority queue is:

   1. "b" - "e" (5)
   2. "s" - "a" (7)
   3. "b" - "f" (7)
4. We pop "b" - "e" (5) and look at the edges leaving node "e":

   • Leaving node "e" and entering node "d" with weight 3 (Total: 5 + 3 = 8)
   • Leaving node "e" and entering node "g" with weight 6 (Total: 5 + 6 = 11)
   • Leaving node "e" and entering node "h" with weight 8 (Total: 5 + 8 = 13)
   • Leaving node "e" and entering node "f" with weight 12 (Total: 5 + 12 = 17 - ignore, "b" - "f" is already 7)
   • Leaving node "e" and entering node "a" with weight 9 (Total: 5 + 9 = 14 - ignore, "s" - "a" is already 7)

   The current priority queue is:

   1. "s" - "a" (7)
   2. "b" - "f" (7)
   3. "e" - "d" (8)
   4. "e" - "g" (11)
   5. "e" - "h" (13)
5. We pop "s" - "a" (7) and look at the edges leaving node "a":

   • Leaving node "a" and entering node "d" with weight 5 (Total: 7 + 5 = 12 - ignore, "e" - "d" is already 8)

   The current priority queue is:

   1. "b" - "f" (7)
   2. "e" - "d" (8)
   3. "e" - "g" (11)
   4. "e" - "h" (13)
6. We pop "b" - "f" (7) and look at the edges leaving node "f":

   • Leaving node "f" and entering node "i" with weight 2 (Total: 7 + 2 = 9)
   • Leaving node "f" and entering node "h" with weight 4 (Total: 7 + 4 = 11 - this replaces the previous "e" - "h" path of 13)
   • Leaving node "f" and entering node "c" with weight 8 (Total: 7 + 8 = 15 - ignore, "s" - "c" was already 4)

   The current priority queue is:

   1. "e" - "d" (8)
   2. "f" - "i" (9)
   3. "e" - "g" (11)
   4. "f" - "h" (11)
7. We pop "e" - "d" (8) and look at the edges leaving node "d":

   • Leaving node "d" and entering node "g" with weight 10 (Total: 8 + 10 = 18 - ignore, "e" - "g" is already 11)

   The current priority queue is:

   1. "f" - "i" (9)
   2. "e" - "g" (11)
   3. "f" - "h" (11)
8. We pop "f" - "i" (9) and look at the edges leaving node "i":

   • Leaving node "i" and entering node "t" with weight 7 (Total: 9 + 7 = 16)
   • Leaving node "i" and entering node "h" with weight 3 (Total: 9 + 3 = 12 - ignore, "f" - "h" is already 11)

   The current priority queue is:

   1. "e" - "g" (11)
   2. "f" - "h" (11)
   3. "i" - "t" (16)
9. We pop "e" - "g" (11) and look at the edges leaving node "g":

   • Leaving node "g" and entering node "t" with weight 12 (Total: 11 + 12 = 23 - ignore, "i" - "t" is already 16)

   The current priority queue is:

   1. "f" - "h" (11)
   2. "i" - "t" (16)
10. We pop "f" - "h" (11) and look at the edges leaving node "h":

    • Leaving node "h" and entering node "t" with weight 5 (Total: 11 + 5 = 16 - ties with our current "i" - "t" path, can be noted as alternate)

    The current priority queue is:

    1. "i" - "t" (16)
11. We pop "i" - "t" (16). We have reached the target node "t" with a shortest path distance of 16. By tracing the predecessors backward, we find the final optimal route shown below.

"s" - "b" - "f" - "i" - "t"