Editing Ford–Fulkerson algorithm (section)

==Non-terminating example==

[[File:Ford-Fulkerson forever.svg|right]]

Consider the flow network shown on the right, with source <math>s</math>, sink <math>t</math>, capacities of edges <math>e_1 = 1</math>, <math>e_2 = r=(\sqrt{5}-1)/2</math> and <math>e_3 = 1</math>, and the capacity of all other edges some integer <math>M \ge 2</math>. The constant <math>r</math> was chosen so, that <math>r^2 = 1 - r</math>. We use augmenting paths according to the following table, where <math>p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</math>, <math>p_2 = \{ s, v_2, v_3, v_4, t \}</math> and <math>p_3 = \{ s, v_1, v_2, v_3, t \}</math>.

{| class="wikitable" style="text-align: center"
! rowspan=2 | Step !! rowspan=2 | Augmenting path !! rowspan=2 | Sent flow !! colspan=3 | Residual capacities
|-
! <math>e_1</math> !! <math>e_2</math> !! <math>e_3</math>
|-
| 0 || || || <math>r^0=1</math> || <math>r</math> || <math>1</math>
|-
| 1 || <math>\{ s, v_2, v_3, t \}</math> || <math>1</math> || <math>r^0</math> || <math>r^1</math> || <math>0</math>
|-
| 2 || <math>p_1</math> || <math>r^1</math> || <math>r^0 - r^1 = r^2</math>|| <math>0</math> || <math>r^1</math>
|-
| 3 || <math>p_2</math> || <math>r^1</math> || <math>r^2</math> || <math>r^1</math> || <math>0</math>
|-
| 4 || <math>p_1</math> || <math>r^2</math> || <math>0</math> || <math>r^1 - r^2 = r^3</math>|| <math>r^2</math>
|-
| 5 || <math>p_3</math> || <math>r^2</math> || <math>r^2</math> || <math>r^3</math> || <math>0</math>
|}

Note that after step 1 as well as after step 5, the residual capacities of edges <math>e_1</math>, <math>e_2</math> and <math>e_3</math> are in the form <math>r^n</math>, <math>r^{n+1}</math> and <math>0</math>, respectively, for some <math>n \in \mathbb{N}</math>. This means that we can use augmenting paths <math>p_1</math>, <math>p_2</math>, <math>p_1</math> and <math>p_3</math> infinitely many times and residual capacities of these edges will always be in the same form. Total flow in the network after step 5 is <math>1 + 2(r^1 + r^2)</math>. If we continue to use augmenting paths as above, the total flow converges to <math>\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r</math>.  However, note that there is a flow of value <math>2M + 1</math>, by sending <math>M</math> units of flow along <math>sv_1t</math>, 1 unit of flow along <math>sv_2v_3t</math>, and <math>M</math> units of flow along <math>sv_4t</math>. Therefore, the algorithm never terminates and the flow does not even converge to the maximum flow.<ref>{{cite journal| title = The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate | first = Uri | last = Zwick|author-link=Uri Zwick | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 148 | issue = 1 | date = 21 August 1995 | pages = 165–170 | doi = 10.1016/0304-3975(95)00022-O| doi-access = free }}</ref>

Another non-terminating example based on the [[Euclidean algorithm]] is given by {{harvtxt|Backman|Huynh|2018}}, where they also show that the worst case running-time of the Ford-Fulkerson algorithm on a network <math>G(V,E)</math> in [[ordinal numbers]] is <math> \omega^{\Theta(|E|)}</math>.

{{Clear}}