The Ford-Fulkerson algorithm (named for L. R. Ford and D. R. Fulkerson) computes the maximum flow in a flow network.
It works by finding a flow augmenting path in the graph. By adding the flow augmenting path to the flow already established in the graph, the maximum flow will be reached when no more flow augmenting paths can be found in the graph. However, there is no certainty that this situation will ever be reached, so the best that can be guaranteed is that the answer will be correct if the algorithm terminates. In the case that the algorithm runs forever, the flow might not even converge towards the maximum flow. However, this situation only occurs with irrational flow values. With integer flow values, the runtime of Ford-Fulkerson is bounded by O(E*|f|), where E is the number of edges in the graph and f is the maximum flow in the graph.
A variation of the Ford-Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds-Karp algorithm.
External links
