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

(a) Explain why Floyd–Warshall Algorithm 9B can be employed to compute the required shortest paths.

(b) Apply Algorithm 9B to compute the length of shortest paths from all nodes 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 only intermediate nodes up to t by showing that values at the end of iteration t = 2 in your computations of part

(b) correspond to lengths of shortest paths using only nodes 1 and 2 as intermediates.