Return to the graph of Exercise 9-1, and suppose that we seek shortest paths from node 1 to all other nodes.

(a) Explain why Bellman–Ford Algorithm 9A can be employed to compute the required shortest paths.

(b) Apply Algorithm 9A to compute the lengths of shortest paths from node 1 to all other nodes.

(c) Use d[k] labels of your computations in part

(b) to recover all optimal paths.

(d) Verify the interpretation of interim labels n1t2[k] as lengths of shortest paths using at most t arcs/edges by showing that values at the end of iteration t = 2 in your computations of part

(b) correspond to lengths of shortest paths using 1 or 2 arcs/

edges.

(e) Determine the maximum number of arcs/

edges in any path of this graph, and explain how this bounds the computation required for Algorithm 9A.