1 Matching Annotations
  1. Mar 2023
    1. 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.