Ford-Fulkerson algorithm
|
|
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. When the capacities are integers, 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. This is because each augmenting path can be found in O(E) time and increases the flow by an integer amount which is at least 1.
A variation of the Ford-Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds-Karp algorithm.
Pseudocode:
- let G be the input graph.
- initialize an array f such that f[e] = 0 for all edges e in G
- while there exists an s -> t path in the residual graph
- choose some path p
- augment(f, p)
- update residual graph
- augment(array f, path p):
- c = lowest capacity edge on p
- for each edge e on p
- if e is a forward edge
- f[e] += c
- if e is a backwards edge
- f[e] -= c
- if e is a forward edge
External links
- Animation of Ford-Fulkerson algorithm (http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml.en)
- Explanation of algorithm (http://is.twi.tudelft.nl/~melissen/Onderwijs/Netwerkoptimalisering%20IN3530/Ford-Fulkerson%20Max%20Flow%20Labeling%20Algorithm.htm)pt:Algoritmo de Ford-Fulkerson