4. (26 pts) Treat the following two parts independently. (H Figl. a) Suppose that Dijkstra's shortest path algorithm is being applied to the network presented in Figure 1 (where all arc lengths are positive), to determine the shortest paths between node A and all other nodes. At the end of the third iteration the lengths of the shortest paths between A and B, D, G have been determined as 2, 5, 10 units respectively (i.e. the permanent labels of nodes B, D, G are 2, 5, 10 respectively). Say True, False or Maybe to the following statements; provide a brief explanation. i) The shortest path to H must pass through G. ii) The shortest path to G must pass through D. iii) The lenght of the arc (A,C) is greater than 10. iv) The lenght of the arc (B, D) is 3. b) Suppose Figurel represents a transportation network where it is desired to maximize the flow from A to H. At a particular iteration of the maximum flow algorithm (the one discussed in class), a total current flow of 34 units is reached and the corresponding residual network (i.e. showing maximum possible additional flow changes on individual arcs) are shown in Figure 2. Answer the following questions. i) Is it possible to increase the total flow from A to H? If yes, show how to increase it; if no, explain why not. ii) Identify the minimum cut between A and H, using the method described in class. That is, give the set of vertices defining the cut and the set of arcs in the cut. What is the capacity of this minimum cut? (Give it without computing the capacities on each individual arc) 2 29 6 18 12 15 8 8 15 20 15 Fig 2