Source code online books for professionals by professionals

Figure 10-4.  A flow network before and after augmenting via an augmenting path (highlighted)
The general Ford-Fulkerson approach, as explained in this section, does not give any running time guarantees. 
In fact, if irrational capacities (containing square roots or the like) are allowed, the iterative augmentation may never 
terminate. For actual applications, the use of irrationals may not be very realistic, but even if we restrict ourselves to 
limited-precision floating-point numbers, or even integers, we can still run into trouble. Consider a really simple network 
with source, sink, and two other nodes, u and v. Both nodes have edges from the source and to the sink, all with a 
capacity of k. We also have a unit-capacity edge from u to v. If we keep choosing augmenting paths that go through the 
edge uv, adding and canceling one unit of flow in every iteration, that would give us 2k iterations before termination.
What’s the problem with this running time? It’s pseudopolynomial—exponential in the actual problem size. We 
can easily crank up the capacity, and hence the running time, without using much more space. And the annoying 
thing is that if we had chosen the augmenting paths more cleverly (for example, just avoiding the edge uv altogether), 
we would have finished in two rounds, regardless of the capacity k.
Luckily, there is a solution to this problem, one that gives us a polynomial running time, no matter the capacities 
(even irrational ones!). The thing is, Ford-Fulkerson isn’t really a fully specified algorithm, because its traversal is 
completely arbitrary. If we settle on BFS as the traversal order (thereby always choosing the shortest augmenting 

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
217
path), we end up with what’s called the Edmonds-Karp algorithm, which is exactly the solution we’re looking for. For 
n nodes and m edges, Edmonds-Karp runs in O(nm
2
) time. That this is the case isn’t entirely obvious, though. For a 
thorough proof, I recommend looking up the algorithm in the book by Cormen et al. (see “References” in Chapter 1). 
The general idea is as follows: Each shortest augmenting path is found in O(m) time, and when we augment the flow 
along it, at least one edge is saturated (the flow reaches the capacity). Each time an edge is saturated, the distance 
from the source (along the augmenting path) must increase, and this distance is at most O(n). Because each edge can 
be saturated at most O(n) times, we get at O(nm) iterations and a total running time of O(nm
2
).
For a correctness proof for the general Ford-Fulkerson method (and therefore also the Edmonds-Karp 
algorithm), see the next section, on minimum cuts. That correctness proof does assume termination, though, 
which is guaranteed if you avoid irrational capacities or if you simply use the Edmonds-Karp algorithm (which has 
a deterministic running time).
One augmentation traversal, based on BFS, is given in Listing 10-3. An implementation of the full Ford-
Fulkerson method is shown in Listing 10-4. For simplicity, it is assumed that s and t are different nodes. By default, the 
implementation uses the BFS-based augmentation traversal, which gives us the Edmonds-Karp algorithm. The main 
function (ford_fulkerson) is pretty straightforward and really quite similar to the previous two algorithms in this 
chapter. The main while loop keeps going until it’s impossible to find an augmenting path and then returns the flow. 
Whenever an augmenting path is found, it is traced backward to s, adding the capacity of the path to every forward 
edge and subtracting (canceling) it from every reverse edge.
The bfs_aug function in Listing 10-3 is similar to the traversal in the previous algorithms. It uses a deque, to get 
BFS, and builds the traversal tree using the P map. It only traverses forward edges if there is some remaining capacity 
(G[u][v]-f[u,v] > 0), and backward edges if there is some flow to cancel (f[v,u] > 0). The labeling consists both  
of setting traversal predecessors (in P) and in remembering how much flow could be transported to this node 
(stored in F). This flow value is the minimum of (1) the flow we managed to transport to the predecessor and (2) the 
remaining capacity (or reverse flow) on the connecting edge. This means that once we reach t, the total slack of the 
path (the extra flow we can push through it) is F[t].
Note
 
■
   If your capacities are integers, the augmentations will always be integral as well, leading to an integral flow. 
This is one of the properties that give the max-flow problem (and most algorithms that solve it) such a wide range of  
application.