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 Dijkstra Algorithm 9C can be employed to compute the required shortest paths.

(b) Apply Algorithm 9C to compute the length 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 n[k] as lengths of shortest paths using only permanently labeled nodes by showing that values after two permanent nodes have been processed in your computations of part

(b) correspond to lengths of shortest paths using only those nodes (and the destination).