Consider the max-flow problem of Fig. 7.18.
(a) Apply the preflow-push algorithm with initial prices p1 = 0, and pi = N -i for i = 2,...,N. Use two different methods to choose the node for iteration: (1) Select the node with highest price, and (2) Select the node with lowest price. Explain why the first method works better, and speculate on the reason why this might be true in general.
(b) Write a computer program to solve the problem of Fig. 7.18 using the preflow-push algorithm with initial prices p1 = N and pi = 0 for i = 2,...,N. Use two different methods to choose the node for iteration: (1) Select the node with highest price, and (2) Select the node at random with equal probability among the possible choices. Plot the number of iterations required with the two methods as a function of N, starting with N = 1000 and up to some reasonable number. Can you make any experimental inferences about computational complexity