Ford-Fulkerson Algorithm: The Fine Print

Learn the implementation details of the Ford-Fulkerson algorithm.

Implementation details

To implement the Ford-Fulkerson algorithm, the first challenge to address is to find a semi-path from a source to a sink in a given flow network. It’s not obvious how to do this efficiently. It is easy to find outgoing edges from a vertex by traversing a single adjacency list, but finding all incoming edges on that vertex requires traversing adjacency lists of all the vertices!

Press + to interact

A significant part of this lesson is aimed at working around the difficulty of finding semi-paths when implementing the Ford-Fulkerson algorithm.

Residual network

To avoid doing all that work, we maintain a second digraph to keep track of edges in both directions. We call this digraph a residual network. We construct a residual network G=(V,E)G^\prime=(V^\prime, E^\prime) for a flow network G=(V,E)G=(V,E) with a flow ff as follows:

  1. VV^\prime is just a copy of VV.
  2. For each edge (u,v)(u,v) in EE, there are two edges (u,v)(u, v) and (v,u)(v, u) in EE^\prime.
  3. We assign capacities to edges in GG^\prime to make it a flow network. For an edge (u,v)(u,v) in GG, the capacities assigned to corresponding two edges in GG^\prime are given by

C(u,v)=C(u,v)f(u,v)C(v,u)=f(u,v)\begin{align*} C^\prime(u,v) &= C(u,v) - f(u,v) \\ C^\prime(v,u) &= f(u,v) \end{align*}

The edge capacities in a residual network represent the maximum amount by which we can increase or decrease the flow along the corresponding edge in GG.

For example, in the following illustration, the flow along the edge (u,v)(u,v) in GG can increase by 22 units or decrease by 55 units. This explains the capacities of (u,v)(u,v) ...

Get hands-on with 1400+ tech skills courses.