Why need (node number - 1) iterations in Bellman Ford algorithm to find shortest paths?

Question

Image: 4 iterations, with (a) is the original graph. (b), (c), (d), (e) correspond to result after each iteration. Example from "Introduction to Algorithm 3rd"

Hi, I do not understand few aspects about the algorithm. I hope someone could help. Below are my questions.

In each iteration, all edges are relaxed, as far as I concern. I expected all the node are updated distance in the first iteration. So why in the first iteration (b), only distance of node t and y are updated but the other still infinity?

Another question is, why need (node number - 1) iterations in which all edges are relaxed? What is guaranteed to achieve at each iteration so that the algorithm must run in (node number - 1) time to make sure the shortest path is found as long as no negative-weight cycles exist?

Answer 1

The reason that only d[y] and d[t] are updated in the first iteration is that these two vertices are the only ones whose estimation of the distance from s can be improved. To be more precise, in order for d[v] to be updated at a particular iteration, there must be an edge (u,v) such that d[u]+w(u,v)<d[v]. That is, we must be able to improve our estimation of the distance from s to v in order to update d[v]. In the first iteration, the value of d[u]=inf for every vertex u (except s). Therefore, if v is not a neighbor of s, then u is not s, and hence the value of d[u]+w(u,v) equals inf+w(u,v)=inf. This means we cannot improve our estimation of d[v]. This is why only the neighbors of s are updated in the first iteration even though the algorithm iterates over all the edges of the graph.

As for why we need n-1 iterations, the following two guarantees are achieved after i iterations:

1. if d[u] is not inf, then there exists a path of length d[u] from s to u.
2. if there is a path from s to u with at most i edges, then d[u] is at most the length of the shortest path from s to u with at most i edges.

The number of edges of the shortest path from s to u cannot exceed n-1 (assuming no negative cycles). Therefore, the two guarantees (which can be proved by induction on i) imply that after n-1 iterations, if there's a simple path of a particular length from s to u, the algorithm finds it.