Ford-Fulkerson Algorithm (FFA)
(Redirected from Ford-Fulkerson Algorithm)
Jump to navigation
Jump to search
A Ford-Fulkerson Algorithm (FFA) is a greedy algorithm that can be applied by a maximum flow system (to solve a maximum flow task).
- Example(s):
- See: Augmenting Path, Flow Network.
References
2017
- (Wikipedia, 2017) ⇒ https://en.wikipedia.org/wiki/Ford–Fulkerson_algorithm Retrieved:2017-6-21.
- The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford, Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a specialization of Ford–Fulkerson.
The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.
- The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford, Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a specialization of Ford–Fulkerson.