1. Suppose that we arrange all directed paths from node s to node t in nondecreasing order of their lengths, breaking ties arbitrarily. The kth shortes(path problem is to identify a path that can be at the kth place in this order. Describe an algorithm to find the kth shortest path for k = 2. (Hint: The second shortest path must differ from the first shortest path by at least one arc.)
2. Suppose that every directed cycle in a graph G has a positive length. Show that a shortest directed walk from node s to node t is always a path. Construct an example for which the first shortest directed walk is a path, but the second shortest directed walk is not a path.