The Ford-Fulkerson Method

Learn about the Ford-Fulkerson method of computing maximum flows.

This lesson will cover a general, high-level strategy to compute maximum flows, called the Ford-Fulkerson method.

Description of the method

Given a flow network G=(V,E,c)G = (V, E, c), the Ford-Fulkerson method iteratively refines a flow ff in the graph, until it becomes a maximum flow.

In the beginning, the flow ff has value 00, or, f(u,v)=0f(u, v) = 0 for all edges (u,v)E(u, v) \in E.

We then search for a path from ss to tt through which we can still push at least a single unit of flow. Such a path is called an augmenting path. We can use it to update our flow ff to a flow of higher value. We repeat this procedure until no augmenting path exists, at which point our flow ff is maximum.

A first attempt of finding augmenting paths

So, let’s look into how we can identify augmenting paths. The first approach might be to look for an ss-tt-path upon which each edge still has capacity remaining, or,

f(u,v)<c(u,v)for all edges (u,v) on the path.f(u, v) < c(u, v) \qquad \text{for all edges } (u, v) \text{ on the path}.

Let’s try this out in an example flow network.

Get hands-on with 1200+ tech skills courses.