5.1.1. The Ford-Fulkerson Algorithm

Every augmenting path algorithm follows the template in the following MaxFlow procedure, known as the Ford-Fulkerson algorithm. The algorithm starts with a feasible \(st\)-flow \(f\) that sends no flow along any edge. Then, as long as there exists an \(st\)-path \(P\) in \(G^f\), the algorithm sends more flow from \(s\) to \(t\) along this path \(P\). We prove below that once there is no \(st\)-path in \(G^f\), \(f\) is a maximum \(st\)-flow in \(G\). So the algorithm terminates and reports \(f\).

PROCEDURE \(\boldsymbol{\textbf{MaxFlow}(G, u, s, t)}\):

---

INPUT:

• A directed graph \(G = (V, E)\)
• A capacity labelling \(u : E \rightarrow \mathbb{R}^+\) of the edges of \(G\)
• A source vertex \(s\)
• A sink vertex \(t\)

OUTPUT:

• A maximum \(st\)-flow \(f : E \rightarrow \mathbb{R}^+\)

---

1.     Set \(f_e = 0\) for all \(e \in E\)
2.     DO FOREVER
3.         \(G^f = {}\)residual network with respect to \(f\)
4.         IF there exists an \(st\)-path \(P\) in \(G^f\) THEN
5.             \(f = \text{Augment}(G, u, f, P)\)
6.         ELSE
7.             RETURN \(f\)

The details of sending flow along an augmenting path \(P\) are implemented as a separate procedure Augment. This procedure initializes the augmented flow \(f'\) to be the same as the current flow \(f\). Then it inspects all edges in \(P\) and finds the minimum residual capacity \(\delta\) of all edges in \(P\). This is the maximum amount of flow we can send along \(P\) without violating the capacity constraint of any edge. Finally, Augment sends \(\delta\) units of flow along \(P\), by reducing the flow of any edge \((y, x)\) such that \((x, y) \in P\) by \(\min\bigl(\delta, f_{y,x}\bigr)\) and increasing the flow along any edge \((x, y)\) such that \((x, y) \in P\) by \(\max\bigl(0, \delta - f_{y,x}\bigr)\). The resulting flow \(f'\) is the new flow to be used in the next iteration of MaxFlow.

PROCEDURE \(\textbf{Augment}(G, u, f, P)\):

---

INPUT:

• A directed graph \(G = (V, E)\)
• A capacity labelling \(u : E \rightarrow \mathbb{R}^+\) of its edges
• A feasible \(st\)-flow \(f\)
• A path \(P\) in the residual network \(G^f\)

OUTPUT:

• An augmented \(st\)-flow \(f'\)

---

1.     Set \(f'_e = f_e\) for all \(e \in E\)
2.     \(\delta = \infty\)
3.     FOR ALL \((x, y) \in P\) DO
4.         \(\delta = \min\left(\delta, u^f_{x,y}\right)\)
5.     FOR ALL \((x, y) \in P\) DO
6.         \(f'_{y,x} = f_{y,x} - \min\bigl(\delta, f_{x,y}\bigr)\)
7.         \(f'_{x,y} = f_{x,y} + \max\bigl(0, \delta - f_{y,x}\bigr)\)
8.     RETURN \(f'\)

Where different augmenting path algorithms differ is in how they find augmenting paths, and this choice can have a significant impact on their running times or in fact on whether the algorithm terminates at all.

For the sake of clarity, the MaxFlow procedure constructs the residual network \(G^f\) from \(G\) and \(f\) in each iteration of the loop. An actual implementation of the algorithm initializes \(G^f = G\) at the beginning of the algorithm (because the flow is zero initially) and then, in each iteration, updates only the edges in \(G^f\) involved in the augmenting path \(P\) found in the current iteration: These are the only edges whose residual capacities or presence or absence in \(G^f\) are affected by changing the flow along the edges in \(P\).