Page 124 - Algorithms Notes for Professionals

the values in d[] will remain the same. Now, if we considered another sequence:

+--------+--------+--------+--------+
| Serial | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Edge | 1->2 | 2->3 | 3->4 |
+--------+--------+--------+--------+

We'd get:

1. d[1] + cost[1][2] = 2 < d[2]. d[2] = 2.
2. d[2] + cost[2][3] = 5 < d[3]. d[3] = 5.
3. d[3] + cost[3][4] = 7 < d[4]. d[4] = 5.

Our very first iteration has found the shortest path from source to all the other nodes. Another sequence 1->2,
3->4, 2->3 is possible, which will give us shortest path after 2 iterations. We can come to the decision that, no matter
how we arrange the sequence, it won't take more than 3 iterations to find out shortest path from the source in this
example.

We can conclude that, for the best case, it'll take 1 iteration to find out the shortest path from source. For the worst
case, it'll take (V-1) iterations, which is why we repeat the process of relaxation (V-1) times.

colegiohispanomexicano.net – Algorithms Notes 120