Why are back edges required in the Ford-Fulkerson algorithm?

Question

To find the maximum flow in a graph, why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back edges? I mean, what is the point calling it a back edge if we assume flow from it?

Answer 1

Back edges are necessary when doing the Ford-Fulkerson algorithm in case the path that you choose ends up not being a part of the overall flow.

As an example where back edges are necessary, consider this flow network:

    s    / \   a   b    \ / \     c   d      \ /       t 

Assume that all edges point down and that all edges have capacity 1 and that you want to find a flow from s to t. Suppose on the first iteration of Ford-Fulkerson that you take the path s → b → c → t. At this point, you've pushed one unit of flow from s to t. If you don't add in any back edges, you're left with this:

    s    /    a   b    \   \     c   d        /       t 

There are no more s-t paths, but that doesn't mean you have a max flow. You can push two units of flow from s to t by sending one along the path s → a → c → t and the other along the path s → b → d → t. Without any back edges in the residual flow network, you would never discover this other path.

Hope this helps!