Question

Show the execution of the Edmonds-Karp algorithm on the flow network of Figure 26.1(a). A flow network G = (V, E) for the Lucky Puck Company's trucking problem. The Vancouver factory is the source s, and the Winnipeg warehouse is the sink t. The company ships pucks through intermediate cities, but only c(u, v) crates per day can go from city u to city v. Each edge is labeled with its capacity. (b) A flow f in G with value |f| = 19. Each edge (u, v) is labeled by f(u, v)/c(u, v). The slash notation merely separates the flow and capacity; it does not indicate division.

Answer 1

26.2-3

Step 1: Use BFS to select the path. The path S - V1 - V3 - t is selected. Nect find the flow that can be sent along the path. The suitable flow is s min(16, 12, 20) = 12. So, sent 12 units along the path. The residual graph is? Step 2: The next shortest path is s - v2 - v4 - t. The flow can be sent through the path is min(13, 14, 4) = 4. The maximum flow is = 12 + 4 = 16 The residual graph is, Step 3: The next shortest path is, s - v2 - v4 - v3 - t. The possible flow on this path is, min(9, 10, 7, 8) = 7 The maximum flow is 12 + 4 + 7 = 23 The residual graph is, There is no path to send a flow s to t. So the maximum flow is 23 and graph is,