Question: Could you help me with problem 1? thanks. Input: A network with single source 1, single sink n, and positive integer capacities u_ij on its
Could you help me with problem 1? thanks.
Input: A network with single source 1, single sink n, and positive integer capacities u_ij on its edges (i, j) Output: A maximum flow x assign x_ij = 0 to every edge (i, j) in the network label the source with infinity, - and add the source to the empty queue Q while not Empty (Q) do i leftarrow Front (Q); Dequeue (Q) for every edge from i to j do//forward edges if j is unlabeled r_ij leftarrow u_ij - x_ij if r_ij > 0 l_j leftarrow mint [l_i, r_ij}; label j with l_j, i^+ Enqueue (Q, j) for every edge from j to i do//backward edges if j is unlabeled if x_ji > 0 l_j leftarrow mint{l_i, x_ji}; label j with l_j, i^- Enqueue (Q, j) if the sink has been labeled //augment along the augmenting path found j leftarrow n//start at the sink and move backwards using second labels while j notequalto 1//the source hasn't been reached if the second label of vertex j is i^+ x_ij leftarrow x_ij + l_n else//the second label of vertex j is i^- x_ji leftarrow x_ji - l_n j leftarrow i erase all vertex labels except the ones of the source reinitialize Q with the source return x//the current flow is maximum (a) What is the value of the flow below? (b)Use the algorithm discussed in class to find an augmenting path? (c) Find the resulting flow? What is the value of the flow? (d) Apply the algorithm once more. What happens? (e) What is the maximum flow in the flow network? (f) What is the cut that shows that this is the maximum flow
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
