Here is the Ford–Fulkerson algorithm again.
Algorithm 19.14 (Ford–Fulkerson).
\begin{algorithmic}
\PROCEDURE{maxflow}{$G = (V,E,s,t,c)$}
\FORALL{$e \in E$}
\STATE $f(e) \gets 0$
\ENDFOR
\STATE $G_f \gets$ residual graph of $G$ and $f$
\WHILE{there is an $s,t$-path $P$ in $G_f$}
\STATE $f = \alpha(f,P)$
\STATE $G_f \gets$ residual graph of $G$ and $f$
\ENDWHILE
\RETURN{$f$}
\ENDPROCEDURE
\end{algorithmic}
One thing that is unclear about this is, like the very first algorithm we saw, the Gale-Shapley algorithm, it's not clear that this algorithm will ever terminate. What if we keep computing flows indefinitely? We already know that we will always get a flow with greater value. All that remains is to observe that every graph has a strict upper bound on the value of any flow: the capacities of the edges directly leaving the source.
Let $G = (V,E,s,t,c)$ be a flow network with $c:E \to \mathbb N$. Then the Ford-Fulkerson algorithm will terminate on $G$.
We observe that the value of any flow cannot exceed the capacity of all edges leaving the source $s$. Let $C = \sum\limits_{(s,v) \in E} f(s,v)$. By Lemma 19.12, the value of any augmented flow $\alpha(f,P)$ will be strictly larger than the flow $f$ that it augments. Therefore, at each iteration of Ford-Fulkerson, the value of the flow maintained by the algorithm increases by at least 1. Since the value of the increases with each iteration and the upper bound on the value of any flow of $G$ is $C$, we can conclude that Ford-Fulkerson will terminate after at most $C$ iterations.
Now, we can consider its running time.
Let $G = (V,E,s,t,c)$ be a flow network with $c:E \to \mathbb N$. Then the Ford-Fulkerson algorithm runs in $O(mC)$ time, where $m = |E|$ and $C = \sum\limits_{(s,v) \in E} f(s,v)$.
Let $m = |E|$ and $n = |V|$ and assume that $m \geq \frac n 2$. By Proposition 20.1, the algorithm must terminate after at most $C$ iterations. Therefore, we can consider the time required for each iteration.
Since each iteration requires $O(m)$ time, the algorithm has running time $O(mC)$ in the worst case. Then we observe that the residual graph $G_f$ has at most $2m$ edges; one forwards and one backwards for each edge of $G$. This means that constructing a residual graph can be performed in $O(m)$ time. To find an $s,t$-path, we simply do a search in $O(m+n) = O(m)$ time. Then finding the augmented flow $\alpha(f,P)$ requires $O(n)$ time, since there are at most $n-1$ edges for any path $P$.
Therefore, one iteration requires $O(m)$ time, which brings us to our total of $O(mC)$ time.
One problem with this algorithm is that it is not necessarily polynomial. A bad case of this would be a flow network with an absurdly large bound of $C$ relative to the size of the graph that updates the flow by increasing by 1 with each iteration. This has to do with the fact that there's no prescribed way to choose an augmenting path.
This goes back to the discussion of Ford and Fulkerson's presentation of the algorithm, which leaves out the how for finding the augmenting path. Without such a definition, we are free to choose the worst case. However, an actual fleshed-out efficient algorithm was given by Edmonds and Karp in 1972 and this algorithm has a running time of $O(|V||E|^2)$.
It remains to show that the Ford-Fulkerson algorithm actually gives us the maximum possible flow. We know a rough upper bound on the flow: the total capacity of all edges leaving the source $s$. However, this is not the best upper bound we can get.
Recall the following definition from our discussion of minimum spanning trees.
Definition 5.8. A cut is a partition of vertices into two nonempty subsets $(S,V-S)$. The cutset of a cut $S$ is the set of edges with exactly one endpoint in $S$.
Suppose we have a cut in our flow network, with $s$ in one set of the partition and $t$ in the other. We observe that the edges in the cutset that move from the $s$ side to the $t$ side constitutes a rough bound on the amount of flow that goes from $s$ to $t$. We can formalize this notion.
An $s,t$-cut is a partition $(S,T)$ of the vertex set $V$ such that $s \in S$ and $t \in T$.
One observation that we can make in the context of flows is that a cut that divides $s$ and $t$ into two different parts of the cut means that flow will necessarily travel from one side of the cut to the other. We can try to quantify some aspects of this.
The capacity of a cut $(S,T)$ is the capacity of all edges leaving $S$, \[c(S,T) = \sum_{(u,v) \in S \times T \subseteq E} c(u,v).\]
Consider the following graph. The vertices highlighted in yellow are in the set $S$, and we consider the cut $(S,T)$. Then the capacity of this cut is the capacity of edges highlighted in cyan, $3+1+5 = 9$.
Note that the capacity of the cut is much lower than the capacity of the edges leaving the source node $s$. Intuitively, it seems like any flow is subject to the capacity of a cut. After all, all flow has to travel from one side of the cut to the other. But we can go further with this: it seems like this should be true for any cut we can define, which leads us to the following problem.
The minimum cut problem is: Given a flow network $G = (V,E,s,t,c)$, find a cut $(S,T)$ with minimum capacity.
If our intuition is correct, then finding a minimum cut will give us a possibly better upper bound on the maximum flow than the outgoing capacity of the source vertex.
Let $f$ be a flow and $(S,T)$ be a cut. Then the value of a flow is the flow leaving $S$ less the flow entering $S$, \[v(f) = \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v).\]
Since there are no edges entering $s$, we have \[v(f) = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) = \sum_{(s,v) \in E} f(s,v).\] By conservation, we have for all $v \in V$, \[\sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w) = 0.\] Then putting the two together, we have \begin{align*} v(f) &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) \\ &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) + 0 \\ &= \sum_{v \in S} \left( \sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w)\right) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v). \end{align*}
Consider the following flow network with cut $(S,T)$, where vertices in $S$ are highlighted in yellow and vertices in $T$ are highlighted in green. The capacities of this network are in pink, while the flow is labeled in blue. We observe that the value of the flow is 9.
The flow leaving $S$ is circled in yellow, for a total of $2+4+9$, while the flow entering $S$ is circled in blue, which totals $6$. The difference in these flows is $2+4+9-6 = 9$, which is the value of our flow.
Of course, the in-flow of $S$ is the out-flow of $T$ and the out-flow of $S$ is the in-flow of $T$, so this lemma can be reformulated in terms of $T$. This lemma leads to the following bound.
Let $f$ be a flow and $(S,T)$ be a cut. Then $v(f) \leq c(S,T)$.
\begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) \\ &\leq c(S,T) \end{align*}
This bound confirms our intutition above, that any cut places an upper bound on the flow for a given network. This means that the minimal cut for a network will give us the best upper bound on the maximum flow through that network.
Let $f$ be a flow and $(S,T)$ be a cut. If $v(f) = c(S,T)$, then $f$ is a max flow and $(S,T)$ is a min cut.
We observe that for any flow $f'$, we have $v(f') \leq c(S,T) = v(f)$. We also have that for any cut $(S',T')$, $c(S',T') \geq v(f) = c(S,T)$.
This leads us to the statement of the Max-Flow Min-Cut theorem.
The value of a maximum flow is the capacity of a minimum cut.
We will use this to show that the Ford-Fulkerson algorithm is correct, by showing that we can compute the minimum cut from it.
Let $G = (V,E,s,t,c)$ be a flow network. Then $f$ is a maxmimum flow if and only if $G_f$ contains no augmenting paths.
We will show that the following are equivalent.
$(1) \implies (2)$ is easy: this is just Corollary 14.8.
$(2) \implies (3)$ is also fairly straightforward. Suppose $G_f$ does have an augmenting path. Then we can augment $f$ and increase the flow, so $f$ wasn't a maximum flow.
So it remains to show that $(3) \implies (1)$. We have that $f$ is a flow such that $G_f$ has no augmenting paths. Then this means that not every vertex in $G_f$ is reachable from $s$, so we let $S$ be the set of vertices reachable from $s$ in $G_f$. This naturally gives us a cut $(S,T)$, since it is clear that $t \not \in S$ (otherwise, there would be an augmenting path in $G_f$).
Now, let's consider the flow on the edges in the cutset of $(S,T)$. If $(u,v)$ is an edge in $G$ with $u \in S$ and $v \in T$. This edge is not a forward edge in $G_f$, since otherwise, $v$ would have been reachable and $v \in S$. Since $(u,v)$ is not a forward edge, this means $(u,v)$ had no unused capacity by $f$, so $f(u,v) = c(u,v)$.
Next, consider an edge $(u',v')$ in $G$ with $u' \in T$ and $v' \in S$. We claim that $f(u',v') = 0$. Suppose not. Then $(v',u')$ is a backward edge in $G_f$ and $u'$ would have been reachable by $s$, which could not be the case since $u' \in T$.
Therefore, all outgoing edges of $S$ are saturated with flow and all incoming edges of $S$ are empty. By the flow value lemma, we have \begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) - 0 \\ &= c(S,T). \end{align*}
Since the Ford-Fulkerson algorithm relies on obtaining the flow for which its residual graph contains no augmenting paths, we can conclude that the flow that the Ford-Fulkerson algorithm returns is the maximum flow.