Page 118 - Algorithms Notes for Professionals

We have selected 1 as the source vertex. We want to find out the shortest path from the source to all other
vertices.

At first, d[1] = 0 because it is the source. And rest are infinity, because we don't know their distance yet.

We will relax the edges in this sequence:

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

You can take any sequence you want. If we relax the edges once, what do we get? We get the distance from source
to all other vertices of the path that uses at most 1 edge. Now let's relax the edges and update the values of d[]. We
get:

1. d[4] + cost[4][5] = infinity + 7 = infinity. We can't update this one.
2. d[2] + cost[3][4] = infinity. We can't update this one.
3. d[1] + cost[1][3] = 0 + 2 = 2 < d[2]. So d[3] = 2. Also parent[1] = 1.
4. d[1] + cost[1][4] = 4. So d[4] = 4 < d[4]. parent[4] = 1.
5. d[4] + cost[4][6] = 9. d[6] = 9 < d[6]. parent[6] = 4.
6. d[2] + cost[2][3] = infinity. We can't update this one.

We couldn't update some vertices, because the d[u] + cost[u][v] < d[v] condition didn't match. As we have said
before, we found the paths from source to other nodes using maximum 1 edge.

Our second iteration will provide us with the path using 2 nodes. We get:

1. d[4] + cost[4][5] = 12 < d[5]. d[5] = 12. parent[5] = 4.
2. d[3] + cost[3][4] = 1 < d[4]. d[4] = 1. parent[4] = 3.
3. d[3] remains unchanged.
4. d[4] remains unchanged.
5. d[4] + cost[4][6] = 6 < d[6]. d[6] = 6. parent[6] = 4.
6. d[3] remains unchanged.

colegiohispanomexicano.net – Algorithms Notes 114