Ford-Fulkerson Algorithm

The Ford - Fulkerson algorithm solves the problem of finding the maximum flow in the transport network .

The idea of the algorithm is as follows. Initially, the value of the stream is assigned the value 0: $f(u,v)=0$ ${\ displaystyle f (u, v) = 0}$ $f (u, v) = 0$ for all $u,v\in V$ ${\ displaystyle u, v \ in V}$ $u, v \ in V$ . Then the flow magnitude iteratively increases by searching for an increasing path (path from source s to drain t , along which a larger flow can be sent). The process repeats until a magnifying path can be found.

Content

Algorithm

Informal Description

Zero all threads. The residual network initially coincides with the original network.
In the residual network, we find any path from the source to the drain. If there is no such way, stop.
We run through the found path (it is called the increasing path or the increasing chain ) the maximum possible flow:
1. On the found path in the residual network, we are looking for an edge with minimal throughput $c_{\min }$ ${\ displaystyle c _ {\ min}}$ .
2. For each edge on the found path, increase the flow by $c_{\min }$ ${\ displaystyle c _ {\ min}}$ , and in the opposite - we reduce by $c_{\min }$ ${\ displaystyle c _ {\ min}}$ .
3. Modify the residual network. For all edges on the found path, as well as for edges opposite to them, we calculate a new throughput. If it became nonzero, add an edge to the residual network, and if it is zero, we erase it.
We return to step 2.

It is important that the algorithm does not specify which path we are looking for in step 2 or how we do it. For this reason, the algorithm is guaranteed to converge only for whole bandwidths, but even for them, with large values of bandwidths, it can work for a very long time. If the throughputs are real, the algorithm can work indefinitely without converging to the optimal solution (see the example below ).

If you search not for any path, but for the shortest, you get the Edmonds – Karp algorithm or the Dinits algorithm . These algorithms converge for any real weights in time $O(|V||E|^{2})$ ${\ displaystyle O (| V || E | ^ {2})}$ and $O(|V|^{2}|E|)$ ${\ displaystyle O (| V | ^ {2} | E |)}$ respectively.

Formal Description

Dan Earl $G(V,E)$ ${\ displaystyle G (V, E)}$ with bandwidth $c(u,v)$ ${\ displaystyle c (u, v)}$ and flow $f(u,v)=0$ ${\ displaystyle f (u, v) = 0}$ for edges from u to v . It is necessary to find the maximum flow from source s to sink t . At each step of the algorithm, the same conditions apply as for all flows:

$\ f(u,v)\leqslant c(u,v)$ ${\ displaystyle \ f (u, v) \ leqslant c (u, v)}$ . Stream out $u$ ${\ displaystyle u}$ at $v$ ${\ displaystyle v}$ does not exceed bandwidth.
$\ f(u,v)=-f(v,u)$ ${\ displaystyle \ f (u, v) = - f (v, u)}$ .
$\ \sum _{v}f(u,v)=0\Longleftrightarrow f_{in}(u)=f_{out}(u)$ ${\ displaystyle \ \ sum _ {v} f (u, v) = 0 \ Longleftrightarrow f_ {in} (u) = f_ {out} (u)}$ for all nodes $u$ ${\ displaystyle u}$ , Besides $s$ ${\ displaystyle s}$ and $t$ ${\ displaystyle t}$ . The flow does not change when passing through the node.

Residual network $G_{f}(V,E_{f})$ ${\ displaystyle G_ {f} (V, E_ {f})}$ - network with bandwidth $c_{f}(u,v)=c(u,v)-f(u,v)$ ${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$ and without flow.

Entry Count $G$ ${\ displaystyle G}$ with bandwidth $c$ ${\ displaystyle c}$ , a source $s$ ${\ displaystyle s}$ and stock $t$ ${\ displaystyle t}$
Output Max Flow $f$ ${\ displaystyle f}$ of $s$ ${\ displaystyle s}$ at $t$ ${\ displaystyle t}$

$f(u,v):=0$ ${\ displaystyle f (u, v): = 0}$ for all the edges $(u,v)$ ${\ displaystyle (u, v)}$
As long as there is a way $p$ {\ displaystyle p} of $s$ {\ displaystyle s} at $t$ {\ displaystyle t} at $G$ $f$ {\ displaystyle G_ {f}} such that $c$ $f$ $($ $u$ $,$ $v$ $)$ $>$ $0$ {\ displaystyle c_ {f} (u, v)> 0} for all ribs $($ $u$ $,$ $v$ $)$ $\in$ $p$ {\ displaystyle (u, v) \ in p} :
1. To find $c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\}$ ${\ displaystyle c_ {f} (p) = \ min \ {c_ {f} (u, v) \; | \; (u, v) \ in p \}}$
2. For each rib $($ $u$ $,$ $v$ $)$ $\in$ $p$ {\ displaystyle (u, v) \ in p}
  1. $f(u,v):=f(u,v)+c_{f}(p)$ ${\ displaystyle f (u, v): = f (u, v) + c_ {f} (p)}$
  2. $f(v,u):=f(v,u)-c_{f}(p)$ ${\ displaystyle f (v, u): = f (v, u) -c_ {f} (p)}$

A path can be found, for example, by a breadth-first search ( Edmonds-Karp algorithm ) or depth-deep search in $G_{f}(V,E_{f})$ ${\ displaystyle G_ {f} (V, E_ {f})}$ .

Difficulty

At each step, the algorithm adds the incremental path stream to the existing stream. If the capacities of all the edges are integers, it is easy to prove by induction that the flows through all the edges will always be integer. Therefore, at each step, the algorithm increases the flow by at least one, therefore, it converges in no more than O ( f ) steps, where f is the maximum flow in the graph. You can complete each step in time O ( E ), where E is the number of edges in the graph, then the total time of the algorithm is limited to O ( Ef ).

If the throughput of at least one of the edges is an irrational number, then the algorithm can work infinitely, without even necessarily converging to the correct solution. An example is given below.

Example of a non-convergent algorithm

Consider the network on the right, with the source $\ s$ ${\ displaystyle \ s}$ by stock $\ t$ ${\ displaystyle \ t}$ bandwidth $\ e_{1}$ ${\ displaystyle \ e_ {1}}$ = $\ 1$ ${\ displaystyle \ 1}$ , $\ e_{2}$ ${\ displaystyle \ e_ {2}}$ = $r=({\sqrt {5}}-1)/2$ ${\ displaystyle r = ({\ sqrt {5}} - 1) / 2}$ , $\ e_{3}$ ${\ displaystyle \ e_ {3}}$ = $\ 1$ ${\ displaystyle \ 1}$ and the throughput of all other edges equal to an integer $M\geq 2$ ${\ displaystyle M \ geq 2}$ . Constant $\ r$ ${\ displaystyle \ r}$ chosen so that $\ r^{2}=1-r$ ${\ displaystyle \ r ^ {2} = 1-r}$ . We use the paths from the residual graph given in the table, and $\ p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}$ ${\ displaystyle \ p_ {1} = \ {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}}$ , $\ p_{2}=\{s,v_{2},v_{3},v_{4},t\}$ ${\ displaystyle \ p_ {2} = \ {s, v_ {2}, v_ {3}, v_ {4}, t \}}$ and $\ p_{3}=\{s,v_{1},v_{2},v_{3},t\}$ ${\ displaystyle \ p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}}$ .

Step	Path found	Added stream	Residual bandwidth
Step	Path found	Added stream	$e_{1}$ ${\ displaystyle e_ {1}}$	$e_{2}$ ${\ displaystyle e_ {2}}$	$e_{3}$ ${\ displaystyle e_ {3}}$
0			$r^{0}=1$ ${\ displaystyle r ^ {0} = 1}$	$r$ ${\ displaystyle r}$	$one$ ${\ displaystyle 1}$
one	$\{s,v_{2},v_{3},t\}$ ${\ displaystyle \ {s, v_ {2}, v_ {3}, t \}}$	$one$ ${\ displaystyle 1}$	$r^{0}$ ${\ displaystyle r ^ {0}}$	$r^{1}$ ${\ displaystyle r ^ {1}}$	$0$ ${\ displaystyle 0}$
2	$p_{1}$ ${\ displaystyle p_ {1}}$	$r^{1}$ ${\ displaystyle r ^ {1}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$	$0$ ${\ displaystyle 0}$	$r^{1}$ ${\ displaystyle r ^ {1}}$
3	$p_{2}$ ${\ displaystyle p_ {2}}$	$r^{1}$ ${\ displaystyle r ^ {1}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$	$r^{1}$ ${\ displaystyle r ^ {1}}$	$0$ ${\ displaystyle 0}$
four	$p_{1}$ ${\ displaystyle p_ {1}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$	$0$ ${\ displaystyle 0}$	$r^{3}$ ${\ displaystyle r ^ {3}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$
five	$p_{3}$ ${\ displaystyle p_ {3}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$	$r^{2}$ ${\ displaystyle r ^ {2}}$	$r^{3}$ ${\ displaystyle r ^ {3}}$	$0$ ${\ displaystyle 0}$

Note that after step 1, as well as after step 5, the residual ability of the edges $e_{1}$ ${\ displaystyle e_ {1}}$ , $e_{2}$ ${\ displaystyle e_ {2}}$ and $e_{3}$ ${\ displaystyle e_ {3}}$ are shaped $r^{n}$ ${\ displaystyle r ^ {n}}$ , $r^{n+1}$ ${\ displaystyle r ^ {n + 1}}$ and $0$ ${\ displaystyle 0}$ , respectively, for some kind of natural $n$ ${\ displaystyle n}$ . This means that we can use magnifying paths. $p_{1}$ ${\ displaystyle p_ {1}}$ , $p_{2}$ ${\ displaystyle p_ {2}}$ , $p_{1}$ ${\ displaystyle p_ {1}}$ and $p_{3}$ ${\ displaystyle p_ {3}}$ infinitely many times, and the residual throughput of these edges will always be in the same form. The total flow after step 5 is $1+2(r^{1}+r^{2})$ ${\ displaystyle 1 + 2 (r ^ {1} + r ^ {2})}$ . For infinite time, the full flow will converge to $\textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r$ ${\ displaystyle \ textstyle 1 + 2 \ sum _ {i = 1} ^ {\ infty} r ^ {i} = 3 + 2r}$ , while the maximum flow is $2M+1$ ${\ displaystyle 2M + 1}$ . Thus, the algorithm not only works infinitely long, but does not even converge to the optimal solution. ^[one]

Example

The following example shows the first steps of the Ford-Fulkerson algorithm in a transport network with four nodes, source A and drain D. This example shows the worst case. When using a breadth-first search, the algorithm only needs 2 steps.

Way	Throughput	Result
	Initial transport network
$A, B, C, D$ ${\ displaystyle A, B, C, D}$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ ${\ displaystyle \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (C, D)) =}$ $\min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))=$ ${\ displaystyle \ min (c (A, B) -f (A, B), c (B, C) -f (B, C), c (C, D) -f (C, D)) =}$ $\min(1000-0,1-0,1000-0)=1$ ${\ displaystyle \ min (1000-0,1-0,1000-0) = 1}$
$A, C, B, D$ ${\ displaystyle A, C, B, D}$	$\min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))=$ ${\ displaystyle \ min (c_ {f} (A, C), c_ {f} (C, B), c_ {f} (B, D)) =}$ $\min(c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D))=$ ${\ displaystyle \ min (c (A, C) -f (A, C), c (C, B) -f (C, B), c (B, D) -f (B, D)) =}$ $\min(1000-0,0-(-1),1000-0)=1$ ${\ displaystyle \ min (1000-0.0 - (- 1), 1000-0) = 1}$
	After the 1998 steps ...
	End network

Links

YouTube task solution example
Algorithm Visualizer
Implementing Ford-Fulkerson Max Stream Search in Java
Wikimedia Commons has media related to the Ford-Fulkerson Algorithm

Literature

Thomas H. Cormen et al. Algorithms: Construction and Analysis = INTRODUCTION TO ALGORITHMS. - 2nd ed. - M .: "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Notes

↑ Zwick, Uri. The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate (English) // Theoretical Computer Science : journal. - 1995 .-- 21 August ( vol. 148 , no. 1 ). - P. 165-170 . - DOI : 10.1016 / 0304-3975 (95) 00022-O .

[1] Zwick, Uri. The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate (English) // Theoretical Computer Science : journal. - 1995 .-- 21 August ( vol. 148 , no. 1 ). - P. 165-170 . - DOI : 10.1016 / 0304-3975 (95) 00022-O .