Figure 6.22 Examples for Exercises 6.12 and 6.13.
Undergraduate based:
Using the shortest augmenting path algorithm, solve the maximum flow problem give in Figure 6.22(b). Describe the augmenting paths at each iteration as well as any advances and/or retreats and the distance labels at each iteration. Verify you have the maximum flow by exhibiting an appropriate cut.
In brief, run the Dinic's algorithm for this graph.