algorithmgraph-theorynetwork-flowford-fulkerson

How can we be sure that paths that uses backward edges in Ford-Fulkerson are the valid ones?


In Ford Fulkerson algorithm for finding maximum flow in a flow network, we use backward edges so that we can improve maximum flow (basically improve already chosen augmenting paths). Without it, chosen augmenting paths aren't guaranteeing that they maximize the flow.

But I have problem with understading why it works. I mean, why can we be sure that some augmenting path that goes via backward edge is the path that could be found in original network flow (in other words, why can we be sure that augmenting path that uses backward edges has it's representation in original graph)? Also, why is maximum flow equal to summation of all found augmenting paths, not only these that guarantee maximum flow?


Solution

  • Intuitively speaking, to find the maximum flow, you would need to sum all possible capacity of all possible paths from starting point flowing to ending point. So Ford-Fulkerson, backward edges are needed because the algorithm (BFS) use to find the path from starting point to end point can't guarantee to be optimal because the flow path might take up edge capacity for the another path to reach the ending point, this would limit the number of possible paths to calculate maximum flow. So backward edges are created as a way to guarantee that another path can still reach the ending point. This could be understood intuitively that, in a pipe system, if a pipe has water flow in from 2 directions (forward and backward edges are used) with similar volume rate, it will also flow out from 2 directions with similar volume rate, rendering the path irrelevant beacuse the water essentially not moving and will still flow to other alternative paths to reach the ending point