1. We define an in-tree of shortest paths as a directed in-tree rooted at a sink node t for which the tree path from any node i to node t is a shortest path. State a modification of the generic label-correcting algorithm that produces an in-tree of shortest paths.
2. Let G = (N1 U N2, A) be a bipartite network. Suppose that n1 = | N1 |, n2 = | N2| and n1 ≤ n2. Show that the FIFO label-correcting algorithm solves the shortest path problem in this network in O(n1m) time.