Run the Bellman-Ford algorithm on the directed graph of figure below, using ver- tex z as the source. In each pass, relax edges in the same order as in the figure, and show the d and pi values after each pass. Now, change the weight of edge (z, x) to 4 and run the algorithm again, using s as the source.

| h(8 M y(0 4 ) 34 1212 | x(4K12)2 S(0 (c) Figure 24.4 The execution of the Bellman-Ford algorithm. The source is vertex S. The d val- ues appear within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then v.T = w. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x,t), (y,x), (y,z), (z,x), (x,s), (s,t), (S, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example