Editing Ford–Fulkerson algorithm (section)

{{Use American English|date = April 2019}}
{{Short description|Algorithm to compute the maximum flow in a network}}
The '''Ford–Fulkerson method''' or '''Ford–Fulkerson algorithm''' ('''FFA''') is a [[greedy algorithm]] that computes the [[maximum flow problem|maximum flow]] in a [[flow network]]. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified<ref>{{Cite book|title = Electronic Design Automation: Synthesis, Verification, and Test|url = https://archive.org/details/electronicdesign00wang|url-access = limited|last = Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng|publisher = Morgan Kaufmann|year = 2009|isbn = 978-0080922003|pages = [https://archive.org/details/electronicdesign00wang/page/n240 204]}}</ref> or it is specified in several implementations with different running times.<ref>{{Cite book|title = Introduction to Algorithms|url = https://archive.org/details/introductiontoal00corm_805|url-access = limited|author1=Thomas H. Cormen |author2=Charles E. Leiserson |author3=Ronald L. Rivest |author4=Clifford Stein |publisher = MIT Press|year = 2009|isbn = 978-0262258104|pages = [https://archive.org/details/introductiontoal00corm_805/page/n734 714]}}</ref> It was published in 1956 by [[L. R. Ford Jr.]] and [[D. R. Fulkerson]].<ref>{{Cite journal | last1 = Ford | first1 = L. R. | author-link1 = L. R. Ford Jr.| last2 = Fulkerson | first2 = D. R. | author-link2 = D. R. Fulkerson| doi = 10.4153/CJM-1956-045-5 | title = Maximal flow through a network | journal = [[Canadian Journal of Mathematics]]| volume = 8 | pages = 399–404 | year = 1956 | s2cid = 16109790 | url = http://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf }}</ref> The name "Ford&ndash;Fulkerson" is often also used for the [[Edmonds–Karp algorithm]], which is a fully defined implementation of the Ford&ndash;Fulkerson method.

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]].