patternMinor
Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?
Viewed 0 times
theflowalwaysstartalgorithmfulkersonwillfordmaxvalid
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#52342, answer score: 6
Revisions (0)
No revisions yet.