Ford Fulkerson : Backedge condition

Question

I was looking into ford fulkerson and got confused with the backedge. can somebody clear me out till what time or what should be the flow/capacity condition for considering backedge in the graph? Since I can consider any edge for backedge subtract that much flow and continue and this process can go on and on.

Please help me.

Thanks

Abhinav

Answer 1

You use a "back edge" only if it's a part of a path P from s to t such that all capacities of the edges on the path greater than 0 (note that any path that fulfills this requirements increases the flow from s to t). An edge may be considered as a "back edge" if there's already flow greater than 0 on that edge, so you can "return" this flow. In that case the capacity of the edge will be the existing flow in it, when you do this, consider the edge's direction as opposite to the original direction.

Think about a graph with only vertices s and t and an edge between them with capacity c. at first you'll send c from s to t. now you can allegedly use this edge as a back edge, but note that when using it as a back edge it is directed from t to s and thus not a path from s to t.

Take a look at the wiki example to see how the back edge is being used there (from that example you can understand why the algorithm's running time is dependent on the edge's capacities).