Bad choice of path in maximum-flow algorithm

51 Views Asked by At

I'm currently studying the maximum-flow algorithm and encountered the following problem: enter image description here The number on each edge is the capacity. I wonder what kind of bad choice can cause so many iterations. Thanks.

1

There are 1 best solutions below

3
On BEST ANSWER

Lets note the two middle vertices $a$ (the upper one) and $b$ (the lower one). Take the path $sabt$. We can push one unit of flow. Now take the path $sbat$. We can also push one unit of flow because arc $ab$ have a flow of 1. Now that we have emptied the arc $ab$, we can again take the path $sabt$, and push one unit of flow. If we continue to take alternately the paths $sabt$ and $sbat$, we will need to take $sabt$ $10^k$ times and $sbat$ $10^k$ times to saturate the arcs.