Example 3: Maximum Flow and Minimum Cut Problem

During peak traffic hours, many cars are travelling from a downtown parkade to the nearest freeway on ramp.  The traffic engineers have decided to widen the road downtown to accomodate this heavy flow of cars traveling between these two points.  Which roads should the engineers widen in order to achieve this goal?

Below is a network that shows the roads connecting the parkade, node A, to the freeway on-ramp, node G.  The arcs are labeled with their directional flow.
ie: This shows that A to B has a capacity of 5, while B to A has a capacity of 0.

Start the demo below to find which roads should be widened.

To begin the example press the start button.  If you would like to step through
the example, press Pause then the Step button.
This animation was created using Jawaa 2.0.  For the Jawaa 2.0 source code, visit www.cs.duke.edu/csed/jawaa2.
For the source code for this animation, click here.