[Solved]: Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

Problem Detail: 

I stumbled across this question and answer (source):

Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.

Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.

Does this mean that the Ford-Fulkerson algorithm will reach max flow if given any valid flow as input, instead of initializing all edges to 0 at the start?

Asked By : Michal Tenenberg

Answered By : Tom van der Zanden

Yes. If the flow is not maximum, then there is an augmenting path. If there's an augmenting path, Ford-Fulkerson will find it (and continue to find them until the flow is maximum). Starting from a different initial flow does not change this.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52342

3.2K people like this

 Download Related Notes/Documents