Maximum Flow

A flow network is a directed graph where each edge is labeled with a capacity (non-negative number) and there are two distinguished vertices: the source $s$ and sink $t$.

A flow is a function $f$ that maps each edge to a number such that

The value of a flow, written $|f|$, is the sum of the flows out of the source minus the flows into the source. $$ |f| = \sum_u f(s,u) - \sum_v f(v,s) $$

The maximum flow problem is to find the flow with the maximum value for a given flow network.

Example Flow Network

Example Flow

In the following graph, we've labeled each edge with two number, written $f:c$, where $f$ is the flow and $c$ is the capacity. The flow value is $4$, the sum of the three out edges of $S$.

Residual Network

The residual network of a flow network $G$ and flow $f$ is another graph $G_f$ with the same vertices as $G$. For each edge $(u,v) \in G$:

The residual network includes just the edges that can be used to add or remove flow from the network.

We can go in the other direction and compute the residual capacity of an edge in the residual network, $e \in G_f$.

The following is the residual network for the example graph. (Ignoring the backward edges for now.)

Instead of explicitly creating the residual network, we sometimes would just like to navigate it by creating its edges on the fly.

Augmenting Paths

An augmenting path is a path from the source to the sink (without cycles) in the residual network.

The residual capacity of an augmenting path is the smallest of the residual capacities of all the edges on the path.

Lemma 26.2 and Corollary 26.3 Given a flow network $G$ and a flow $f$, you can add the residual capacity of any augmenting path in $G_f$ to all the edges in the path to obtain a new flow $f'$ and $|f'| > |f|$.

We can find an augmenting path by applying Depth-First Search to the residual network. The following is an augmenting path in the example graph with a residual capacity of $1$.

And here's the flow network with the residual capacity added to the flows on the augmenting path.

The Ford-Fulkerson method repeatedly finds augmenting paths and adds their residual capacity to the flow.

It stops when it can no longer find an augmenting path.

But does that coincide with finding the maximum flow?

Max-flow Min-Cut Theorem

This theorem will tell us that a flow is maximum if and only if there are no augmenting paths in the residual network.

But first we have to learn what a min-cut is.

A cut $(S,T)$ of a flow network includes the source on one side $S$ and the sink on the other $T$.

The net flow across a cut $f(S,T)$ is the sum of the flows from $S$ to $T$ minus the flows from $T$ to $S$.

The capacity of a cut $c(S,T)$ is the sum of the capacities of the edges that cross from $S$ to $T$.

The minimum cut of a network is a cut whose capacity is minimum with respect to all other cuts.

Lemma 26.4 The net flow across any cut is equal to the value of the flow.

The following is a cut in the example graph. The net flow across this cut is $4$ which indeed matches the flow value (the sum of the flows leaving $S$). The capacity of this cut is $11$.

Corollary 26.5 The value of every flow is no larger than the capacity of any cut.

Theorem 26.6 (Max-flow min-cut theorem) The following conditions are equivalent:

  1. $f$ is a maximum flow
  2. $G_f$ contains no augmenting paths
  3. $|f| = c(S,T)$ for some cut $(S,T)$. Proof We first show that (1) implies (2). Towards a contradiction, suppose there is an augmenting path. We add its residual capacity to $f$ to get a greater flow, but that contradicts that $f$ is a maximum flow.

Next we show that (2) implies (3). Since there are no augmenting paths, we create a cut $S$ of all the nodes reachable from the source in the residual graph and put the rest in $T$. By Lemma 26.4, we have $$ |f| = f(S,T) $$ and by definition, $$ f(S,T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{v\in T}\sum_{u\in S} f(v,u) $$

Thus, the above equation simplifies to $$ f(S,T) = \sum_{u\in S} \sum_{v\in T} c(u,v) $$ which means $$ f(S,T) = c(S,T) $$

Finally, we show that (3) implies (1). So there is a cut $(S,T)$ such that $|f| = c(S,T)$. Suppose $f'$ is another flow. By Corollary 26.5, $|f'| \leq c(S,T)$. So $|f'| \leq |f|$.


Ford-Fulkerson Algorithm for Maximum Flow

The algorithm performs the following steps:

  1. Initialize the flow on every edge to 0.
  2. Compute the residual network G_flow and look for an augmenting path aug_path.
  3. If there is no augmenting path, return the current flow.
  4. Otherwise, augment the flows on the path with the residual capacity and go to step 2.

Ford-Fulkerson on the Example Graph

The following shows each step of the Ford-Fulkerson algorithm on the example graph. Some augmenting paths involve a "backward" edge in the residual graph, which we depict as a blue edge in the graph. The augmenting path traverses the backward edge in reverse, which removes some flow from that edge and adds it to another edges.

Time Complexity of Ford-Fulkerson

Edmonds-Karp Algorithm for Maximum Flow

The Edmonds-Karp algorithm is almost the same as Ford-Fulkerson but it instead uses Breadth-First Search to find augmenting paths.

Time Complexity of Edmonds-Karp

The Edmonds-Karp algorithm has time complexity $O(n m^2)$. This is because the number of iterations through the while loop is $O(nm)$ (explained below) and the body of the loop is $O(m)$.

By using BFS we restrict the search for augmenting paths to shortest paths.

Consider the distance from the source to all other vertices in the residual network. That distance either stays the same or increases after each augmentation. The reason is that when we augment the flow, at least one edge $(u,v)$ on a shortest path is removed from the residual graph, causing the distances to vertices further down the path to possibly increase. That edge may get added back later via flow through its "backward" edge, but when it does, it will be via a strictly longer path. Here's why:

Now, a path can only get so long, up to the number of vertices. So the maximum number of times we can augment the flow is the number of edges times the number of vertices: $O(nm)$.

Goldberg's Push-Relabel Algorithm

The push-relabel approach to computing maximum flow is more efficient than Edmonds-Karp, with an $O(n^3)$ time complexity. It is based on the following ideas:

At the beginning, the source is placed at height $n$ and all other vertices at height $0$. The neighbors of the source are given excess flow equal to the capacity of the edge from the source. The source is given a negative excess equal to the capacities of its out-edges.


The push operation can be applied along an edge when the source node has positive excess flow, the residual capacity of the edge is positive, and the height of the source is one greater than the target.

The push operation moves as much of the excess flow as it can (up to the residual capacity of the edge) from the source to the target of the edge. It also updates the flow for the edge. We'll explain the update_overflow function later.

A saturating push is a push that increases the flow on the edge to be equal to the capacity. A saturating push causes the edge to be removed from the residual network.


The relabel operation is applicable to a node when it contains excess flow and all of its neighbors in the residual network are at equal or greater height.

The relabel operation increase the height of the node to one greater than the lowest of its neighbors.

We'll use the following function to display the excess flow and height of each node.

Push and Relabel Examples

Consider again the following example network that has been initialized as described above.

Node A has excess flow but no downhill neighbors, so we raise it to height 1.

Now we can push the excess from node A to node C.

Similarly, we can relabel C and then push 2 units of its excess to T.

Implementation of Goldberg's Push-Relabel Algorithm

By repeatedly pushing and relabeling, the maximum flow will eventually reach the sink T.

However, there is often some excess flow remaining in some of the vertices. That means the flow does not yet satisfy the "flows-in equals flows-out" constraint.

So the process of pushing and relabeling continues, raising many of the vertices above the source vertex and returning all the excess flow to the source.

For efficiency, we'd like to quickly identify nodes that can be relabeled or from which we can push some flow. Those are nodes that are overflowing, i.e., that have positive excess flow. So we maintain a list of nodes named overflow. The update_overflow function adds or removes the given node from the overflow.

The algorithm proceeds as follows:

Time Complexity of Goldberg's Push-Relabel Algorithm

Let $n$ be the number of vertices in the graph and $m$ the number of edges.

So the total time is dominated by the number of non-saturating pushes. Assuming $n < m$, the time complexity is $O(n^2 m)$.