Ford-Fulkerson

General Information

Algorithmic problem: Max-Flow Problems
Prerequisites:
Type of algorithm: loop
Auxiliary data:

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] ierations [math]\displaystyle{ f }[/math] is a fleasible flow.
Variant: The value of [math]\displaystyle{ f }[/math] increases.
Break condition: There is no flow-augumenting path.

Induction Basis

Abstract view: We start with some feasible flow, for example, the zero flow.

Implementation: [math]\displaystyle{ \forall a \in A:f(a):=0. }[/math]

Proof: Obvious.

Induction Step

Abstract view: Find a flow-augmenting path and increase [math]\displaystyle{ f }[/math] along this path by the maximal value such that the flow value of each [math]\displaystyle{ a\in A }[/math] remains in the interval [math]\displaystyle{ [0...c(a)] }[/math].
Implementation:

1. Apply a graph traversal algorithm from [math]\displaystyle{ s }[/math] as follows:
   1. if [math]\displaystyle{ f(v,w)\lt c(v,w) }[/math], [math]\displaystyle{ (v,w)\in A }[/math] can be used for going forward in the direction [math]\displaystyle{ v \rightarrow w }[/math];
   2. if [math]\displaystyle{ f(v,w)\gt 0 }[/math], [math]\displaystyle{ (v,w)\in A }[/math] can be used for going forward in the direction [math]\displaystyle{ w\rightarrow v }[/math]; .
2. Terminate this graph traversal once either is seen or all reachable nodes were seen (whatever occurs first).
3. In the latter case, the break condition of the loop applies.
4. Otherwise,
   1. let [math]\displaystyle{ p }[/math] denote the current path of the traversal (which is an [math]\displaystyle{ (s,t) }[/math]-path in this case);
   2. let [math]\displaystyle{ x }[/math] denote the minimum of the values [math]\displaystyle{ c(a)-f(a) }[/math] on all forward arcs of [math]\displaystyle{ p }[/math];
   3. let [math]\displaystyle{ y }[/math] denote the minimum of the values [math]\displaystyle{ f(a) }[/math] on all backward arcs of [math]\displaystyle{ p }[/math].
   4. For each arc [math]\displaystyle{ a \in A }[/math] on [math]\displaystyle{ p }[/math], increase the flow value by [math]\displaystyle{ min \{x,y \} }[/math] if [math]\displaystyle{ a }[/math] is a forward arc on [math]\displaystyle{ p }[/math], otherwise, decrease the flow value by [math]\displaystyle{ min \{x,y \} }[/math].

Correctness: If the graph traversal does not hit [math]\displaystyle{ t }[/math], the break condition is fulfilled, so nothing is to show. So consider the case that the graph traversal does hit [math]\displaystyle{ t }[/math]. Then [math]\displaystyle{ p }[/math] is an [math]\displaystyle{ (s,t) }[/math]-path. By definition of [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], the capacity constraints are preserved. To see that the flow conservation conditions are preserved as well, only the internal nodes [math]\displaystyle{ p }[/math] of are relevant. Let [math]\displaystyle{ v }[/math] be such an internal node, and let [math]\displaystyle{ u }[/math] and [math]\displaystyle{ w }[/math] denote the immediate predecessor and successor of [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math], respectively. Basically, there are four cases:

• Either [math]\displaystyle{ (u,v) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (v,u) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.
• Either [math]\displaystyle{ (v,w) }[/math] is on [math]\displaystyle{ p }[/math] as a forward arc or [math]\displaystyle{ (w,v) }[/math] is on [math]\displaystyle{ p }[/math] as a backward arc.

It is easy to check preservation of the flow conservation conditions for each of these four cases.

Pseudocode

B-TREE-FIND(x,k)
1  i = 1
2 while i ≤ x.n and k > x.keyi 
3        i = i + 1
4 if i ≤ x.n and k == x.keyi 
5        return (x.i)
6 elseif  x.leaf
7        return NIL
8 else DISK-READ(x.ci) 
9        return B-TREE-FIND(x.ci,k)

Complexity

Statement: If all capacity values are integral, the asymptotic worst-case complexity is [math]\displaystyle{ \Omicron (m*F) }[/math], where [math]\displaystyle{ m = |A| }[/math] and [math]\displaystyle{ F }[/math] is the maximum total flow value.

Proof: A graph search from [math]\displaystyle{ s }[/math] requires [math]\displaystyle{ \Omicron (m) }[/math] . Obviously, determining [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] and changing the flow values along [math]\displaystyle{ p }[/math] requires [math]\displaystyle{ Omicron m }[/math] as well. It is also evident that, after iterations, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval [math]\displaystyle{ [0...F] }[/math], this may happen at most [math]\displaystyle{ F }[/math] times.