Algorithms · Lecture Notes

Chapter 8: Network Flow

A city's water network, a country's highway system, and the links of a data center all ask the same question: how much can be sent from one point to another without exceeding the carrying limits of the links? On graphs this question is written as the maximum flow problem. The chapter first defines flow networks, the constraints a flow must satisfy, and the value of a flow. It then builds the concepts that all the algorithms share: the residual network, the augmenting path, and the cut. The max-flow min-cut theorem proves why a flow that has been found is optimal. The Ford-Fulkerson method, Edmonds-Karp, Dinic's algorithm, and the push–relabel algorithm are then run step by step on the same example networks. The code of each is traced line by line, and the source of its running-time bound is shown. The chapter closes with a comparison of the algorithms and applications such as bipartite matching.

Learning outcomes

Modeling
Model a problem as a flow network of a source, a sink, and edges with capacities; write the capacity and conservation constraints of a flow.
Residual network and cut
Compute the residual network, an augmenting path, and its bottleneck; find the capacity of an s–t cut and apply the max-flow min-cut theorem.
Algorithms
Run the Ford-Fulkerson, Edmonds-Karp, Dinic, and push–relabel algorithms step by step on an example network.
Analysis
Explain where the bounds O(E · |f*|), O(V · E²), and O(V² · E) come from; compare the algorithms and choose a suitable one.

8.1Flow networks

The questions asked about graphs so far have mostly concerned paths: is there a path between two vertices, which path is shortest, which tree connects all vertices most cheaply? Network flow asks something different. Finding one path is not enough; many paths are used at once, and they share edges. Every edge has a carrying limit. The question is how much all the paths can carry together.

This question comes up often in everyday life. Water in a pipeline, traffic on a road network, and data packets in a computer network are all flows. Each pipe carries at most its own capacity. Water does not accumulate at junctions: whatever enters a junction also leaves it. These two observations become the two basic constraints of the flow network model.

8.1.1The maximum flow problem

The model is a directed graph with two special vertices. The vertex the flow leaves is called the source, and the vertex it arrives at is the sink. The source is written s and the sink t. Every edge has a capacity: the largest amount that can pass through that edge per unit time.

Definition 8.1

A flow network consists of a directed graph G = (V, E), two distinct vertices s, t ∈ V, and a function that assigns each edge (u, v) a nonnegative capacity c(u, v) ≥ 0. For a pair (u, v) that is not in the graph, c(u, v) = 0 is assumed. The maximum flow problem is to find the largest amount of flow that can be sent from the source to the sink without exceeding the capacities.

The same small network is used for much of the chapter. Figure 8.1 shows it. There are six vertices and seven edges; the edge labels are capacities. The source is S and the sink is T.

4343266SABCDT
Figure 8.1: The example flow network. The edge labels are capacities: S→A 4, S→C 3, A→B 4, B→C 3, B→T 2, C→D 6, D→T 6. The maximum flow in this network is 7.

That the maximum flow is 7 must be seen from two sides. First, 7 units can be sent; a flow that shows this will be given shortly. Second, more than 7 cannot be sent. This second claim is clear at once from the source. The capacities of the two edges leaving S sum to 4 + 3 = 7. Every unit leaving the source has to use one of these two edges. Hence no more than 7 can reach the sink. This simple observation is the first example of the cut concept that comes later.

The same reasoning can be made at the sink. The capacities of the edges entering T sum to 2 + 6 = 8. This is also an upper bound, but it is looser than 7. The smaller of the two bounds is the valid one. An upper bound that is always correct is this: the maximum flow cannot exceed the sum of the capacities leaving the source or the sum of the capacities entering the sink. This bound is not always tight; the bottleneck can also lie in the middle of the network.

8.1.2Flows and their constraints

A flow assigns each edge the amount passing through it. For this assignment to make sense, two rules must hold.

Definition 8.2

A flow is a function that assigns each edge (u, v) a number f(u, v) and satisfies the following two constraints:

  • Capacity constraint: for every edge, 0 ≤ f(u, v) ≤ c(u, v).
  • Flow conservation: for every vertex v other than s and t, Σu f(u, v) = Σw f(v, w); that is, the flow in equals the flow out.

The value of a flow is |f| = Σv f(s, v) − Σv f(v, s): the net flow leaving the source.

The capacity constraint expresses the carrying limit of a pipe. A flow cannot be negative; a pipe does not run backward. Nor can it exceed the capacity. The conservation constraint says that intermediate vertices are not storage tanks. Every unit that enters an intermediate vertex must leave it somewhere. The source and the sink are exempt from this rule: the source produces flow and the sink consumes it.

The subtraction term in the definition of the value may seem unnecessary at first. In our example network no edge enters the source, so this term is zero. In a general network, however, there may be edges returning to the source. If 5 units leave the source and 1 unit returns, 4 units have actually been sent into the network. This is why the value is the net flow leaving the source. Thanks to conservation, this net flow equals the net flow entering the sink: since no intermediate vertex accumulates flow, everything leaving the source eventually arrives at the sink.

4/43/34/42/32/25/65/6SABCDT
Figure 8.2: A flow of value 7 in the same network. The labels have the form flow/capacity. Into C come 3 + 2 = 5 units and 5 units leave; |f| = 4 + 3 = 7.
Example 8.1

Let us check that the flow in Figure 8.2 is valid.

Capacity constraint. Edge by edge: 4 ≤ 4, 3 ≤ 3, 4 ≤ 4, 2 ≤ 3, 2 ≤ 2, 5 ≤ 6, 5 ≤ 6. No edge exceeds its limit.

Conservation. There are four intermediate vertices.

  • A: in f(S, A) = 4, out f(A, B) = 4.
  • B: in f(A, B) = 4, out f(B, C) + f(B, T) = 2 + 2 = 4.
  • C: in f(S, C) + f(B, C) = 3 + 2 = 5, out f(C, D) = 5.
  • D: in f(C, D) = 5, out f(D, T) = 5.

Value. |f| = f(S, A) + f(S, C) = 4 + 3 = 7. Check from the sink side: f(B, T) + f(D, T) = 2 + 5 = 7. The two numbers are equal.

In this flow some edges are filled to their limit. An edge with f(u, v) = c(u, v) is called a saturated edge; no more flow can be sent through it. In the flow shown, S→A, S→C, A→B, and B→T are saturated. That both edges leaving the source are saturated explains why the flow cannot be increased. Saturated edges are part of the cuts that explain why the maximum flow cannot be larger.

Common mistake

Thinking that the value of a flow is the sum of the flows on all edges. In the flow shown, the edge flows sum to 4 + 3 + 4 + 2 + 2 + 5 + 5 = 25, but the value of the flow is 7. The same unit of flow passes through many edges along its path and is counted again on each. The value is read only from the edges at the source (or the sink).

8.1.3Multiple sources and sinks

Real problems rarely have a single source and a single sink. Several factories ship goods to several warehouses; several servers stream data to several groups of users. The way to solve this without a separate algorithm is a small graph transformation.

S∞s₁∞s₂∞sₙt₁∞t₂∞tₘ∞T⋮⋮network
Figure 8.3: Supersource and supersink. A new vertex S is joined by edges of infinite capacity to all the sources si, and all the sinks tj are joined by edges of infinite capacity to a new vertex T.

Two new vertices are added to the network: a supersource S and a supersink T. For each old source si an edge S → si is added, and for each old sink tj an edge tj → T. These edges are given unlimited (∞) capacity. The new edges therefore never become a bottleneck; the flow is limited only by the edges of the old network. In the new network the maximum flow from S to T equals the total flow that can be sent from all the sources to all the sinks in the old network. In practice, any number larger than the sum of all capacities of the old network can stand in for ∞.

The transformation can be adapted to other restrictions. For example, if factory s1 can produce at most 50 units, the edge S → s1 is given capacity 50 instead of ∞. The same idea is used in problems where vertices also have capacities: a vertex is split into two parts, and an edge with the vertex's capacity is placed between the two parts. This method will be taken up again under applications.

8.2The residual network and augmenting paths

The first way to find a maximum flow that comes to mind is a greedy method. Find a path from the source to the sink through edges that are not full, send as much flow along it as it can carry, and keep doing this until no path is left. This method sometimes gives the correct result and sometimes does not. The problem is that early decisions cannot be undone. A badly chosen path can fill edges in a way that other paths could have used better. The solution is to build the possibility of undoing flow already sent into the model. The structure that does this is the residual network.

8.2.1The residual network

Definition 8.3

Under a flow f, the residual capacity of an edge is defined in two ways. For every edge (u, v) of the original network:

  • Forward edge: cf(u, v) = c(u, v) − f(u, v). This is the amount that can still be sent through the edge.
  • Backward edge: cf(v, u) = f(u, v). This is the amount of the flow already sent that can be undone.

The residual network Gf consists only of the edges with cf > 0.

The residual network shows the changes that can still be made under the current flow. A forward edge says “I can send more in this direction.” A backward edge says “I can take back part of what I sent in this direction.” Figure 8.4 shows this on a single edge. The edge u → v of capacity 5 carries 3 units of flow. In the residual network this edge turns into two edges: the forward edge u → v for the remaining 2 units and the backward edge v → u for the 3 units that can be undone.

3/5uv 23uv
Figure 8.4: (a) An edge in the flow network: flow 3, capacity 5. (b) Its counterpart in the residual network: a forward edge of 5 − 3 = 2 units (solid arrow) and a backward edge of 3 units (dashed arrow).

The two extreme cases are instructive too. If the flow is zero, the capacity of the backward edge is zero and the backward edge does not enter the residual network; the residual network is identical to the original network. If the edge is saturated, the capacity of the forward edge is zero and only the backward edge remains in the residual network. Each original edge produces at most two edges in the residual network. The number of edges of the residual network is therefore at most 2E.

Example 8.2

Let us build the residual network of the flow in Figure 8.2. Two numbers are computed for each edge: the forward residual capacity c − f and the backward residual capacity f.

  • S→A (4/4): forward 0, backward A→S 4.
  • S→C (3/3): forward 0, backward C→S 3.
  • A→B (4/4): forward 0, backward B→A 4.
  • B→C (2/3): forward B→C 1, backward C→B 2.
  • B→T (2/2): forward 0, backward T→B 2.
  • C→D (5/6): forward C→D 1, backward D→C 5.
  • D→T (5/6): forward D→T 1, backward T→D 5.

Once the zeros are dropped, ten edges remain in the residual network. No residual edge leaves S; S has only incoming backward edges. Hence there is no path from S to T in the residual network. The meaning of this observation will be explained shortly: the flow is maximum.

8.2.2What a backward edge means

A backward edge is not a physical pipe. There need not be a real connection in the direction v → u. A backward edge is a bookkeeping entry: it shows that flow previously sent from u to v can be cancelled. “Sending” δ units along a backward edge means reducing f(u, v) by δ.

Why does this cancellation help? If an augmenting path uses the backward edge v → u, the path replaces the old flow arriving at v from u with its own. The old flow from u to v is now freed, and along the rest of the path it goes from u in another direction. In effect the flow is rearranged: some units abandon their old routes and switch to new ones. Conservation continues to hold at every vertex. Thanks to backward edges the algorithm can correct its first wrong choices. A concrete example of this correction appears in the second Ford-Fulkerson example.

Common mistake

Interpreting a backward edge as a real edge added to the network, or as “sending flow backward.” Flow does not increase in the direction of the backward edge; the flow on the forward edge decreases: f(u, v) −= δ. For this reason no edge has negative flow in the final flow, and backward edges add no capacity to the original network.

8.2.3Augmenting paths and bottlenecks

Definition 8.4

An augmenting path is a directed path from the source to the sink in the residual network Gf. The bottleneck of the path is the smallest residual capacity among its edges: cf(p) = min { cf(u, v) : (u, v) ∈ p }.

Every edge on an augmenting path has positive residual capacity. That is, the path passes either through forward edges that carry less than their capacity or through the reverse directions of edges that carry flow. The most flow that can be sent along the path is the capacity of its narrowest edge. This is the flow counterpart of the saying that a chain is only as strong as its weakest link.

4343266SABCDT
Figure 8.5: The augmenting path S → A → B → T (highlighted) in the initial residual network. The residual capacities are 4, 4, and 2; the bottleneck is min(4, 4, 2) = 2, and it comes from the edge B→T.

If the flow is initially zero everywhere, the residual network is identical to the original network and an augmenting path is an ordinary directed path. Augmenting paths are usually found with depth-first search (DFS) or breadth-first search (BFS). Which search is used does not change the value of the resulting flow, but it changes greatly how many steps the algorithm takes. This difference is the starting point of the Edmonds-Karp algorithm.

8.2.4Augmenting the flow along a path

Once an augmenting path p and its bottleneck δ = cf(p) have been found, the flow is updated as follows. For every edge (u, v) on the path:

  • If (u, v) is an edge of the original network (a forward edge), f(u, v) is increased by δ.
  • If (u, v) is a backward edge, that is, the original edge is (v, u), then f(v, u) is decreased by δ.
Theorem 8.1 (Augmentation)

Let f be a flow, p an augmenting path in the residual network, and δ = cf(p). The f' obtained by the update above is again a flow, and |f'| = |f| + δ.

Capacity. On a forward edge the new flow is f(u, v) + δ ≤ f(u, v) + cf(u, v) = c(u, v). On a backward edge the new flow is f(v, u) − δ ≥ f(v, u) − cf(u, v) = 0. In both cases the flow stays in the interval [0, c].

Conservation. Consider an intermediate vertex v on the path. The path enters v along one edge and leaves along one edge. If the incoming edge is a forward edge, the flow into v increases by δ; if it is a backward edge, the flow out of v decreases by δ. In either case the “in minus out” difference of v changes by +δ. By a similar argument for the outgoing edge, the difference changes by −δ. The total change is zero; conservation is not broken.

Value. Since the path is simple, it uses the source only once, on its first edge. This edge leaves the source. If it is a forward edge, the flow leaving the source increases by δ; if it is a backward edge, the flow entering the source decreases by δ. In both cases the net outflow increases by δ. □

This theorem is the foundation of all augmenting-path algorithms. With every augmentation the value of the flow strictly increases and the flow remains valid. Two questions remain. When no augmenting path is left, is the flow really maximum? How many augmentations are needed? The first question is answered with cuts. The answer to the second depends on how the path is chosen.

The update has two more important consequences. The residual capacity of the bottleneck edge is exactly δ; after the update this residual capacity drops to zero. So with every augmentation at least one edge on the path leaves the residual network. Also, for every edge on the path, δ units of residual capacity appear in the opposite direction. The residual network thus changes a little with each augmentation: some edges disappear and some backward edges appear.

8.3Cuts

To prove that a flow is maximum, we must show that no larger flow exists. Trying all flows one by one is impossible. The cut concept instead gives an upper bound as a single number. The edges between the side containing the source and the side containing the sink are like a “border gate” that the flow must pass through. The width of the gate limits the flow that can pass.

8.3.1The s–t cut and its capacity

Definition 8.5

An s–t cut (S, T) is a partition of the vertex set V into two disjoint sets with s ∈ S and t ∈ T. The capacity of the cut is the sum of the capacities of the edges going from S to T:

c(S, T) = Σu ∈ S, v ∈ T c(u, v)

A cut of smallest capacity is called a minimum cut.

In the definition a cut is a partition of the vertices, not a set of edges. The cut edges come out of this partition: the edges with one endpoint in S and the other in T. If these edges are deleted from the network, no directed path from the source to the sink remains. In computing the capacity, only the edges going from S to T are counted. Edges going from T to S are not added to the capacity, because they are not what prevents the flow from reaching the sink.

4343266cutSTSABCDT
Figure 8.6: The cut S = {S, A} and T = {B, C, D, T}. The edges crossing the dashed line from left to right are A→B (4) and S→C (3): c(S, T) = 4 + 3 = 7.

In the cut of Figure 8.6 the edge B→C also crosses the dashed line, but it goes from the T side to the T side; both of its endpoints are in T. For this reason it is not counted. Similarly, both endpoints of the edge S→A are on the S side.

Example 8.3

The example network has four intermediate vertices: A, B, C, D. Each can be placed on the S side or the T side, so there are 24 = 16 s–t cuts in all. Let us compute a few.

  • S = {S}: the cut edges are S→A and S→C; 4 + 3 = 7.
  • S = {S, A, B}: the cut edges are S→C (3), B→C (3), B→T (2); total 8.
  • S = {S, C}: S→A (4) and C→D (6); total 10. The edge B→C goes from T to S and is not counted.
  • S = {S, B, D}: S→A (4), S→C (3), B→C (3), B→T (2), D→T (6); total 18. A→B and C→D go from T to S.

When all the cuts have been computed, the smallest capacity is 7, and two cuts attain this value: {S} and {S, A}. The minimum cut need not be unique.

Table 8.1: Some s–t cuts in the example network. The smallest of the sixteen cuts is 7.
S sideEdges from S to Tc(S, T)
{S}S→A 4, S→C 37
{S, A}A→B 4, S→C 37
{S, A, B}S→C 3, B→C 3, B→T 28
{S, A, B, C, D}B→T 2, D→T 68
{S, C}S→A 4, C→D 610
{S, B, D}S→A 4, S→C 3, B→C 3, B→T 2, D→T 618
Common mistake

Taking the minimum cut to be the partition that cuts the fewest edges. A minimum cut minimizes the capacity sum, not the number of edges. Cutting a single edge of capacity 100 is more expensive than cutting three edges of capacity 1. The number of edges measures the same thing as the capacity only when all capacities are 1.

8.3.2Net flow across a cut

The net flow across a cut is found by subtracting the total flow on the edges going from T to S from the total flow on the edges going from S to T:

f(S, T) = Σu ∈ S, v ∈ T f(u, v) − Σu ∈ S, v ∈ T f(v, u)

Unlike capacity, net flow also counts the edges in the backward direction, because flow that comes back must be subtracted from the flow that crosses over.

Theorem 8.2 (Cuts and flows)

For every flow f and every s–t cut (S, T), f(S, T) = |f|. Hence |f| ≤ c(S, T).

For every vertex in S, write the “out minus in” difference and add up these differences. For the source the difference is |f| by definition. The other vertices of S are intermediate vertices (the sink is in T); by conservation their differences are zero. So the total is |f|.

The same sum can also be computed edge by edge. An edge with both endpoints in S appears once in the outflow of one vertex and once in the inflow of another; their contributions cancel. Only the edges crossing the cut remain. Those going from S to T appear with a plus sign in the total, and those going from T to S with a minus sign. This is exactly f(S, T). Therefore f(S, T) = |f|.

For the inequality, use f(u, v) ≤ c(u, v) on forward edges and f(v, u) ≥ 0 on backward edges: |f| = f(S, T) ≤ Σ c(u, v) − 0 = c(S, T). □

What the theorem says agrees with intuition. All the flow leaving the source must cross the cut somewhere to reach the sink. If some flow comes back, it too has to cross forward at least one more time. In the end the net amount crossing the cut equals the amount sent into the network. Let us test the flow of Figure 8.2 on the cut {S, A}: the forward edges are A→B (4) and S→C (3), there is no backward edge; the net flow is 7. On the cut {S, C} the forward edges are S→A (4) and C→D (5), and the backward edge is B→C (2); the net flow is 4 + 5 − 2 = 7. The two cuts differ, but the net flow is the same.

The second half of the theorem says that every cut is an upper bound for every flow. The value of any flow cannot exceed the capacity of any cut. Hence the maximum flow cannot exceed the capacity of the minimum cut. This is an inequality. The real surprise is that the inequality is always an equality.

8.3.3The max-flow min-cut theorem

Theorem 8.3 (Max-flow min-cut)

For a flow f the following three statements are equivalent (Ford and Fulkerson, 1956):

  1. f is a maximum flow.
  2. The residual network Gf has no augmenting path.
  3. For some cut (S, T), |f| = c(S, T).

Consequently, the value of the maximum flow equals the capacity of the minimum cut.

(1) ⇒ (2). If there were an augmenting path in the residual network, then by Theorem 8.1 the flow could be increased by the bottleneck. This contradicts the maximality of f.

(2) ⇒ (3). Let S be the set of vertices reachable from the source in the residual network, and T = V − S. The source is in S. Since there is no augmenting path, the sink is not in S; (S, T) is an s–t cut. For an edge (u, v) with u ∈ S and v ∈ T we must have f(u, v) = c(u, v); otherwise cf(u, v) > 0 and v would also be reachable. For the same reason, on an edge (v, u) going from T to S we must have f(v, u) = 0; otherwise the backward edge u → v would be in the residual network. By Theorem 8.2, |f| = f(S, T) = Σ c(u, v) − 0 = c(S, T).

(3) ⇒ (1). No flow can exceed the capacity of any cut. If |f| = c(S, T), then no flow can be larger than c(S, T), and therefore than |f|. □

The theorem has three separate uses. First, it proves the correctness of augmenting-path algorithms: it is safe to stop when no path is left. Second, it gives an easily checked certificate that a flow is maximum. A flow whose value equals the capacity of some cut is maximum without any other computation. Third, it shows how to find a minimum cut: the vertices reachable from the source in the final residual network form the S side.

The flow found in our example network has value 7, and the capacity of the cut {S} is also 7. The third statement of the theorem holds; the flow is maximum. In the residual network built in Example 8.2 nowhere could be reached from the source. The reachable set is only {S}, and this is exactly the cut in the proof.

8.3.4Finding the minimum cut

The proof of the theorem is also an algorithm. After a maximum flow has been found, a search is run from the source in the final residual network. The visited vertices form the S side. The original edges with one endpoint visited and the other not are the edges of the minimum cut. The following Java method does this. It uses the residual matrix holding the residual capacities and a copy of the original capacities.

List<int[]> minCut(int source, int[][] capacity) {
  boolean[] visited = new boolean[V];
  Queue<Integer> queue = new LinkedList<>();
  queue.add(source);
  visited[source] = true;
  while (!queue.isEmpty()) {          // BFS in the final residual network
    int u = queue.poll();
    for (int v = 0; v < V; v++)
      if (!visited[v] && residual[u][v] > 0) {
        visited[v] = true;
        queue.add(v);
      }
  }
  List<int[]> cut = new ArrayList<>();
  for (int u = 0; u < V; u++)          // original edges from S to T
    for (int v = 0; v < V; v++)
      if (visited[u] && !visited[v] && capacity[u][v] > 0)
        cut.add(new int[]{u, v});
  return cut;
}

The first half of the method is an ordinary BFS. The only difference is that the existence of an edge is tested with residual[u][v] > 0: the search moves only through the residual network. The second half scans all pairs of vertices and adds to the list those pairs with visited[u] true and visited[v] false that have an edge in the original network. The capacity condition matters. Backward edges occupy space in the residual matrix but do not exist in the original network; they cannot be cut edges.

With an adjacency matrix the BFS takes O(V²) and the pair scan takes O(V²). The total time is O(V²), which is negligible next to the cost of finding the maximum flow. The extra memory is O(V + k) for the visited array, the queue, and the result list, where k is the number of edges in the cut. When the method is later run on the final residual network of the second Ford-Fulkerson example, it returns the edges S→1 (10) and 3→4 (9). The total, 19, equals the maximum flow in that network.

8.3.5Overview of network flow algorithms

All the algorithms that find a maximum flow reach the same goal with the same concepts. They differ in the order and in the pieces in which they grow the flow. Table 8.2 summarizes the four algorithms treated in this chapter.

Table 8.2: Network flow algorithms. |f*| is the value of the maximum flow; the running time of Ford-Fulkerson holds for integer capacities.
AlgorithmApproachTimeNote
Ford-Fulkerson (1956)any augmenting path (often DFS)O(E · |f*|)simple; the time depends on the flow value
Edmonds-Karp (1972)shortest augmenting path (BFS)O(V · E²)the polynomial-time form of Ford-Fulkerson
Dinic (1970)level graph + blocking flowO(V² · E)faster than Edmonds-Karp; very efficient on unit capacities
Push–relabel (1988)preflow + heights, local operationsO(V² · E)searches for no paths; the FIFO version runs in O(V³)

The first three algorithms rest on the idea of the augmenting path and maintain a valid flow at every step. The fourth is different: in its intermediate steps it temporarily violates conservation and repairs it only at the end. The years in the table also hold an interesting detail. Dinic's algorithm was published in 1970 in the Soviet Union, before Edmonds-Karp; the two works are independent.

8.4The Ford-Fulkerson method

8.4.1The idea of the method

The Ford-Fulkerson method rests on the work published by L. R. Ford Jr. and D. R. Fulkerson in 1956. It finds the maximum flow between two vertices in a directed graph with capacities. The idea is a natural consequence of the concepts built so far: the flow starts at zero, and as long as an augmenting path is found in the residual network, the flow is increased along that path by the bottleneck. When no path is left, the loop stops; the max-flow min-cut theorem guarantees that the result is optimal.

1. build the residual network2. search for an augmenting path3. send the bottleneck amountrepeatno path:stop
Figure 8.7: The Ford-Fulkerson loop: build the residual network, search for an augmenting path, send the bottleneck amount, and repeat. If no path is found, the loop ends.

Most sources call Ford-Fulkerson a method rather than an “algorithm.” The reason is that it does not specify how the augmenting path is to be found. Any path is accepted. The version that searches for the path with DFS is usually known as Ford-Fulkerson; the version that uses BFS has a name of its own: Edmonds-Karp. That the choice of path affects the running time but not the result will be clear in the comparison of these two versions.

8.4.2The steps of the algorithm

  1. Initialization. f(u, v) = 0 on all edges. Since the flow is zero, the residual capacity of every edge is its own capacity; the residual network is identical to the original network.
  2. Path search. An augmenting path p is searched for in the residual network from the source to the sink. Only edges with cf > 0 are used.
  3. Bottleneck. δ = min cf(u, v), (u, v) ∈ p is computed. This is the most flow that can be sent along the path.
  4. Augmentation. δ units of flow are sent along the path: on forward edges f(u, v) += δ, on backward edges f(v, u) −= δ; |f| += δ. At least one edge on the path becomes saturated.
  5. Repeat. Steps 2–4 are repeated until no augmenting path is left. When the loop ends, |f| is maximum.

In an implementation the flow and the residual capacity need not be stored separately. Only the residual capacities can be kept. When flow is added, the residual capacity of the forward edge decreases by δ and that of the backward edge increases by δ. The flow on an edge is recomputed when needed as f(u, v) = c(u, v) − cf(u, v). The Java code on the slides follows this route.

8.4.3Example 1: step by step

Let us run the method on the network of Figure 8.1. Initially all flows are zero and the residual network is the same as the original. The order of the paths in this example is the order that a search choosing the path with the fewest edges each time would give. Since Ford-Fulkerson accepts any path, this order is valid.

First augmentation. p = S → A → B → T. The residual capacities are 4, 4, and 2; the bottleneck is 2 units and comes from B→T. Two units are sent along the path: |f| = 2. B→T becomes saturated. In the residual network 2 units remain on each of S→A and A→B, and backward edges of 2 units each appear in the opposite directions.

Second augmentation. p = S → C → D → T. The residual capacities are 3, 6, and 6; the bottleneck is 3. |f| = 2 + 3 = 5. S→C becomes saturated. 3 units remain on each of C→D and D→T.

Third augmentation. The only residual edge leaving S is S→A (2 units). From A one can go to B with 2 units. B→T is saturated, but B→C is empty (3 units). C→D and D→T have 3 units each. The path is p = S → A → B → C → D → T, and the bottleneck is min(2, 2, 3, 3, 3) = 2. |f| = 7.

22322323333SABCDT 4/43/34/42/32/25/65/6SABCDT|f| = 7
Figure 8.8: The third augmentation. (a) The path S → A → B → C → D → T in the residual network (highlighted); the dashed arrows are the backward edges of the previous two augmentations. (b) The flow after 2 units have been added along the path; |f| = 7.

After the third augmentation both edges leaving S are saturated. Nowhere can be reached from the source in the residual network; the loop ends.

4341221515SABCDT 4/43/34/42/32/25/65/6SABCDT|f| = 7
Figure 8.9: (a) The final residual network: no residual edge leaves S; only the backward edges A→S and C→S remain. (b) The maximum flow: |f| = 7. The minimum cut is ({S}, the rest), with capacity 4 + 3 = 7.
Table 8.3: The augmentations in Example 1.
AugmentationPathResidual capacitiesBottleneck|f|Saturated edge
1S→A→B→T4, 4, 222B→T
2S→C→D→T3, 6, 635S→C
3S→A→B→C→D→T2, 2, 3, 3, 327S→A, A→B

The final flow is the same as the flow in Figure 8.2: 2 units on B→C and 5 units on C→D. This is a coincidence. The value of the maximum flow is unique, but its distribution over the edges need not be. In the same network, a flow carrying 1 unit on B→T, 3 on B→C, and 6 each on C→D and D→T is also valid, and its value is again 7. The only thing that does not change is that the two edges leaving the source are saturated; the minimum cut {S} forces this.

8.4.4Example 2: using a backward edge

In the first example no augmenting path used a backward edge. To see why backward edges are necessary, a somewhat larger network is needed. In the network of Figure 8.10 the source is S and the sink is T; the intermediate vertices are numbered 1 to 4.

1010428961010S1234T
Figure 8.10: The second example network. Capacities: S→1 10, S→3 10, 1→2 4, 1→3 2, 1→4 8, 3→4 9, 4→2 6, 2→T 10, 4→T 10.

This time the order of the paths is deliberately bad: the first path makes a decision that must be corrected later.

  1. p = S → 1 → 4 → T: residual capacities 10, 8, 10; the bottleneck is 1 → 4 (8). |f| = 8.
  2. p = S → 3 → 4 → T: only 10 − 8 = 2 units are left on 4 → T. The bottleneck is 2; |f| = 10. 4 → T becomes saturated.
  3. p = S → 3 → 4 → 1 → 2 → T: 3 → 4 has 9 − 2 = 7, the backward edge 4 → 1 has 8 (the flow sent to 1 → 4 in the first step), 1 → 2 has 4, and 2 → T has 10 units. The bottleneck is 4; |f| = 14.
  4. p = S → 1 → 4 → 2 → T: 2 units were left on S → 1. On 1 → 4 there is now room for 8 − 4 = 4 units. The bottleneck is 2; |f| = 16.
  5. p = S → 3 → 4 → 2 → T: the bottleneck is 3 → 4 (9 − 6 = 3 left). |f| = 19.

The third step is the heart of the example. When the backward edge 4 → 1 is used, the flow on 1 → 4 drops from 8 to 4. What this means is the following: the 4 units that previously went from 1 to 4 now arrive at 4 from 3. The 4 units freed up at 1 head for the sink along 1 → 2. Conservation is not broken at any vertex. The total flow into 4 and the total flow out of 1 do not change; only their routes change.

28824287261010S1234T 8/106/104/40/24/86/90/64/1010/10S1234T|f| = 14
Figure 8.11: The third augmentation. (a) The path S → 3 → 4 → 1 → 2 → T in the residual network; 4 → 1 is a backward edge. (b) The flow afterward: the flow on 1 → 4 fell from 8 to 4, 1 → 2 filled up with 4 units; |f| = 14.
101942269151910S1234T 10/109/104/40/26/89/95/69/1010/10S1234T|f| = 19
Figure 8.12: (a) The final residual network: from S only 3 can be reached (highlighted vertices). (b) The maximum flow, 19. The minimum cut ({S, 3}, the rest): S→1 (10) + 3→4 (9) = 19.

In the final residual network S → 1 is saturated; 1 unit is left on S → 3, but the only edge leaving 3, 3 → 4, is saturated. The set reachable from the source is {S, 3}. The original edges leaving this set are S → 1 and 3 → 4; both are full. The edge 1 → 3 goes from the T side to the S side and carries no flow. This is a perfect example of the conditions in the proof: forward edges full, backward edges empty.

8.4.5Why are backward edges necessary?

Consider a greedy method that never uses backward edges in the same network. This method searches only for paths through forward edges that are not full.

Example 8.4

Let the first choice again be S → 1 → 4 → T, and send 8 units. Then:

  • S → 3 → 4 → T: 2 units (4 → T becomes saturated). Total 10.
  • S → 1 → 2 → T: 2 units, since 2 units are left on S → 1. Total 12.
  • S → 3 → 4 → 2 → T: there are 7 units on 3 → 4, 6 on 4 → 2, and 8 on 2 → T; 6 units. Total 18.

Now S → 1 is full. From S one can go only to 3, and from there to 4. Both exits of 4 (4 → 2 and 4 → T) are full. The method gets stuck and stops at 18. Yet the maximum flow is 19.

The loss is a single unit, but the principle matters. The first path loaded 8 units onto the edge 1 → 4. Part of this flow should actually have gone through 1 → 2, which would have freed room on the edge 3 → 4. A method that works with forward edges only cannot undo this decision. In the residual network with backward edges, however, the edge 4 → 1 makes it possible to undo part of this decision: the flow coming from 1 is redirected to 2, and the flow coming from 3 to 4. The result is 19, equal to the minimum cut. There is a general rule here: in the residual network with backward edges, the method reaches the maximum whatever order the paths are chosen in.

Common mistake

Forgetting backward edges. Searching with forward edges only is a greedy algorithm and may miss the maximum (18 < 19 in the example). In code the backward edges are often a single line: residual[v][u] += flow. If this line is deleted, the program still runs and returns a number; the problem is noticed only when the result is verified.

8.4.6Pseudocode

The pseudocode of the method is below. Here the flow values are kept in a separate flow table, and the residual capacity is computed when needed as capacity − flow.

FORD_FULKERSON(G, source, sink):
  flow[u, v] = 0, for each (u, v) in E     // 0 at the start
  maxFlow = 0
  while an augmenting path exists:
    path = DFS(G, source, sink, flow)            // edges with c − flow > 0
    delta = ∞                                    // smallest residual capacity on the path
    v = sink
    while v ≠ source:
      u = path.parent[v]
      delta = min(delta, capacity[u, v] − flow[u, v])
      v = u
    v = sink                                     // update the flows on the path
    while v ≠ source:
      u = path.parent[v]
      flow[u, v] += delta
      flow[v, u] −= delta                        // backward edge
      v = u
    maxFlow += delta
  return maxFlow, flow

The outer loop runs as long as an augmenting path is found. The DFS call searches for a path through edges of positive residual capacity and reports the path through a parent array (parent[] in the code) that stores the predecessor of each vertex. The path itself is not stored as a list; it is read back from the sink to the source by following parent.

The first inner loop finds the bottleneck. v starts at the sink; at each step u = path.parent[v], the vertex from which v was reached. delta is limited by the smallest residual capacity seen so far. The loop ends when it reaches the source. The second inner loop walks the same path once more and updates the flow: delta is added in the forward direction and subtracted in the backward direction. The subtraction in the backward direction follows from keeping the flow in a skew-symmetric table: flow[v, u] = −flow[u, v]. In this representation the residual capacity of the backward edge is capacity[v, u] − flow[v, u] = 0 − (−flow[u, v]) = flow[u, v], the same value as in the definition.

This skew-symmetric representation simplifies the code. There is no need for a separate “is it a backward edge?” question; forward and backward edges are handled by the same formula. There is one subtlety: if there are original edges in both directions between two vertices (for example both 1 → 2 and 2 → 1), the flows of the two edges can cancel in the same cell. In the matrix representation this causes no problem, because only the net flow matters.

8.4.7Java: an augmenting path with DFS

The Java implementation on the slides keeps the residual capacities in the matrix residual[u][v]. At the start this matrix is filled with the capacities; the residual capacity of backward edges is zero. The DFS that finds the augmenting path is as follows:

boolean dfs(int u, int sink,
            boolean[] visited, int[] parent) {
  visited[u] = true;
  if (u == sink) return true;
  for (int v = 0; v < V; v++) {
    if (!visited[v] && residual[u][v] > 0) {
      parent[v] = u;
      if (dfs(v, sink, visited, parent))
        return true;
    }
  }
  return false;   // no path to the sink from this branch
}

The method takes four parameters: the current vertex u, the sink, the visited marks, and the parent array that records the path. The first line marks u as visited. This way the same vertex is not entered again and the search does not fall into a cycle. If u is the sink, a path has been found and true is returned.

The loop tries all vertices in order; in an adjacency matrix, “neighbor” means a v with residual[u][v] > 0. When an unvisited neighbor with positive residual capacity is found, parent[v] = u is written and the search continues from v. If the recursive call returns true, this true is passed up at once; the rest of the loop is not tried. If all neighbors are tried and the sink cannot be reached, the method returns false: there is no path to the sink from this branch.

The visited marks are not cleared on return. This is important. If there is no path to the sink from a vertex, reaching that vertex by another route does not change the outcome; trying it again is wasted work. This way each vertex is visited at most once. With an adjacency matrix each visit scans V cells; one DFS takes O(V²). With an adjacency list the same search takes O(V + E).

When flow is added, residual[u][v] −= d and residual[v][u] += d are performed. The backward edge is not created separately; the second line brings it into existence by itself. On the next call the DFS sees this cell as positive and uses the backward edge like an ordinary edge. This assignment is the only place where the code “knows” about backward edges.

8.4.8Code trace: a dead end and a backward edge

Let us run the code on the network of Figure 8.1. Let the vertex order be S, A, B, C, D, T (indices 0 to 5); the DFS tries neighbors in this order. This order produces different paths from those in Example 1. The first DFS finds the path S → A → B → C → D → T (bottleneck 3). In the second DFS, B → C is saturated and the path S → A → B → T carries 1 unit. After two augmentations |f| = 4. Let us trace the third search in detail.

4343113333SABCDT
Figure 8.13: The residual network after two augmentations (|f| = 4). The dashed arrows are backward edges. S→A and A→B are saturated; the backward edge C→B has 3 units and the backward edge B→A has 4 units.
Table 8.4: Trace of the calls dfs(S, T, visited, parent) for the third augmenting path.
StepCallEventparent
1dfs(S)S→A: residual 0, skipped; S→B: no edge. S→C: residual 3 > 0, C not yet visited.parent[C] = S
2dfs(C)C→S: S visited; C→A: 0. C→B: residual 3 > 0 (backward edge).parent[B] = C
3dfs(B)B→S: 0. B→A: residual 4 > 0 (backward edge).parent[A] = B
4dfs(A)A→S: residual 4, but S is visited. The others are 0. Dead end: false.—
5dfs(B) continuesB→C: C visited; B→D: no edge. B→T: residual 1 > 0.parent[T] = B
6dfs(T)u = T is the sink: true. Every call passes true upward.—

The dead end in the fourth step is characteristic behavior of DFS. A was reached by a backward edge, but there is no residual path from A to the sink. The only positive residual edge of A leads back to the source, and the source has already been visited. The search leaves A and continues from where it left off at B. The record parent[A] = B is not erased, but it is harmless: when the path is read back from the sink, A is never visited.

4343113333SABCDT 42141223333SABCDT
Figure 8.14: (a) A dead end at A: the search descended along S → C → B → A and cannot proceed from A. (b) The residual network after 1 unit has been added along the path found, S → C → B → T; |f| = 5.

The path is read back from the sink: parent[T] = B, parent[B] = C, parent[C] = S. The path is S → C → B → T. The bottleneck is min(3, 3, 1) = 1. This augmentation uses the backward edge C → B: the flow on B → C drops from 3 to 2. What this means is that one unit of the flow going from B to C now goes directly to the sink along B → T; the new unit from the source makes up the lost input of C.

The fourth DFS finds the path S → C → D → T and adds 2 units. |f| = 7. The fifth DFS cannot go anywhere from the source and returns false. This version makes 4 augmentations, whereas the order in Example 1 made 3. The final flow of the two versions is the same: the flow of Figure 8.2.

8.4.9Complexity and integrality

The running time of Ford-Fulkerson depends on the structure of the network and on the capacities. Each round has two parts. Finding an augmenting path (DFS or BFS) and updating the flow take O(E); an adjacency list is assumed. The real question is the number of rounds.

Theorem 8.4 (Integrality)

If all capacities are integers, then at every step of the Ford-Fulkerson method the flow and the residual capacities are integers. The method makes at most |f*| augmentations and finishes in O(E · |f*|) time. The maximum flow found has an integer value.

By induction: at the start the flow is zero and the residual capacities equal the capacities; all are integers. If the residual capacities are integers, the bottleneck is also an integer and is at least 1. The update adds integers to or subtracts them from integers, so integrality is preserved. Every augmentation raises the value of the flow by at least 1, and the value cannot exceed |f*|. So at most |f*| augmentations are made, each taking O(E). □

The integrality property has an important application. In problems such as matching, each edge is either used or not; half an edge is meaningless. If the capacities are set to 1, the theorem guarantees that the maximum flow is 0 or 1 on every edge. The flow can then be read directly as a selection.

The bound has a flaw: O(E · |f*|) is not polynomial. The running time of an algorithm is measured by the length of the input, that is, the number of bits needed to write it. A capacity of 109 is written with about 30 bits, but |f*| can be as large as the number itself. Bounds of this kind are called pseudo-polynomial. If the capacities are small integers there is no problem. With large capacities, however, the method can slow down badly if it chooses paths poorly.

If capacities may be irrational numbers, the situation is even worse. In known examples, with badly chosen paths the augmentations become smaller and smaller and the method never terminates; the flow value does not even converge to the maximum flow. Since computers store capacities with finite precision, this does not occur in practice. But it should be kept in mind as the price of the method's “any path” freedom.

8.4.10A bad choice of paths

10001000110001000sabt
Figure 8.15: The worst-case network. The four outer edges have capacity 1000, and the middle edge a → b has capacity 1. The maximum flow is 2000.

In the network of Figure 8.15 the maximum flow is 2000: each of the paths s → a → t and s → b → t carries 1000 units. Two augmentations suffice. Now consider a bad choice of paths. Let the first path be s → a → b → t. Because of the middle edge the bottleneck is 1. This augmentation creates the backward edge b → a. Let the second path be s → b → a → t; because of the backward edge the bottleneck is again 1, and a → b becomes empty again. If these two paths continue to be chosen in turn, every augmentation adds only 1 unit. Reaching the maximum takes 2000 augmentations.

If the capacities were 109, the same choice would require 2 · 109 augmentations. Yet the network has only four vertices and five edges. DFS does not always make this bad choice. For example, a DFS that tries neighbors in index order finishes in 4 augmentations on this network: first s → a → b → t (1), then s → a → t (999), s → b → a → t (1), and s → b → t (999). But no rule prevents DFS from making the bad choice. For this reason the time bound remains O(E · |f*|).

Edmonds-Karp, the version that works with BFS, chooses shortest paths. In this network the shortest paths have two edges: s → a → t and s → b → t. Each carries 1000 units; 2 augmentations suffice. The three-edge path through the middle is never chosen. How BFS removes the dependence on the size of the capacities is the subject of the next section.

Common mistake

Thinking that Ford-Fulkerson runs in polynomial time. O(E · |f*|) depends on the values of the capacities; in a network of the same structure, the time can grow as the capacities grow. Edmonds-Karp and Dinic remove this dependence.

8.5The Edmonds-Karp algorithm

8.5.1The idea: the shortest augmenting path

The Edmonds-Karp algorithm is a variant of the Ford-Fulkerson method. Jack Edmonds and Richard Karp published it in 1972; Dinic reached the same idea independently in 1970. The algorithm fixes the method's one free decision: the augmenting path is found by breadth-first search. Because BFS advances from the source layer by layer, the first path by which it reaches the sink is the one with the fewest edges. In every round Edmonds-Karp chooses this shortest augmenting path.

sabctdBFS: s → c → t (2 edges)
Figure 8.16: BFS chooses the augmenting path with the fewest edges. Here s → c → t has two edges; the three-edge paths (s → a → b → t, s → c → d → t) are not chosen in that round.

Here “short” means the number of edges, not capacity or weight. The capacities of the edges do not affect the length of a path. This choice may look arbitrary at first. But the root of the trouble in the bad-path example was that a long, narrow path was chosen again and again. Choosing the shortest paths prevents such vicious circles. The steps of the algorithm are as follows:

  1. Use BFS to find the shortest augmenting path from the source to the sink in the residual network.
  2. Send the bottleneck amount of flow along the path and update the backward edges.
  3. Repeat these two steps until BFS cannot reach the sink.

It is useful to note from the start that BFS has two different uses in network flow. Edmonds-Karp uses BFS directly to find an augmenting path, and after each BFS it processes a single path. Dinic's algorithm, by contrast, uses BFS to tell whether the sink is still reachable and to build a level graph; in that graph it processes many paths at once.

8.5.2Complexity: O(V · E²)

Each round consists of one BFS and one path update: O(E). The real contribution of Edmonds-Karp is that the number of augmentations has a bound independent of the capacities. The justification of this bound rests on two observations.

Let d(v) denote the number of edges on the shortest path from the source to a vertex v in the residual network. First observation: as Edmonds-Karp runs, the value d(v) of no vertex decreases. An augmentation removes some edges on the path from the residual network and adds some backward edges. Each added backward edge is the reverse of an edge (u, v) on a shortest path; that is, it goes from v to u in a pair with d(v) = d(u) + 1. Such an edge moves a vertex one step farther away and cannot shorten any path.

Second observation: The edge that determines the bottleneck in an augmentation is called a critical edge; it leaves the residual network after the augmentation. In every augmentation at least one edge is critical. When an edge (u, v) is critical, d(v) = d(u) + 1. For the same edge to return to the residual network, an augmenting path must use its backward edge (v, u). At that moment d'(u) = d'(v) + 1. Since distances do not decrease, d'(u) = d'(v) + 1 ≥ d(v) + 1 = d(u) + 2. So the distance of u grows by at least 2 between two times the edge is critical.

Theorem 8.5 (Edmonds-Karp)

The Edmonds-Karp algorithm makes at most O(V · E) augmentations and finishes in O(V · E²) time. The time does not depend on the values of the capacities.

Each time an edge becomes critical, the distance of the vertex at its tail grows by at least 2. The distance starts at 0 and can be at most V − 1 for a reachable vertex; if the vertex becomes unreachable, the edge is never used again. So an edge becomes critical at most about V/2 times. The residual network has at most 2E edges. Since at least one edge is critical in every augmentation, the number of augmentations is O(V · E). Since each augmentation takes O(E), the total time is O(V · E) · O(E) = O(V · E²). □

The meaning of the bound is clear in the worst-case network. Whether the capacities are 1000 or 109, Edmonds-Karp finishes in 2 augmentations. The time no longer depends on |f*|; the algorithm runs in polynomial time. The price is a full BFS in every augmentation. The bound is pessimistic: in practice the number of augmentations stays far below V · E. In networks with V = 6 and E = 9 the bound allows about 27 augmentations; in the examples of these notes the number of augmentations is between 3 and 4.

8.5.3Java: an augmenting path with BFS

The only difference between Edmonds-Karp and Ford-Fulkerson is the function that searches for the path; the main loop is the same. The BFS version is as follows:

boolean bfs(int source, int sink, int[] parent) {
  boolean[] visited = new boolean[V];
  Queue<Integer> queue = new LinkedList<>();
  queue.add(source);
  visited[source] = true;
  parent[source] = -1;
  while (!queue.isEmpty()) {
    int u = queue.poll();
    for (int v = 0; v < V; v++)
      if (!visited[v] && residual[u][v] > 0) {
        queue.add(v);
        parent[v] = u;
        visited[v] = true;
      }
  }
  return visited[sink];
}

In every call the method creates a new visited array. The queue starts with the source; the source counts as visited and parent[source] = -1 is written. This −1 is a marker that tells, when the path is read back, that the source has been reached. In the loop the vertex u at the head of the queue is removed. Then all v are tried in order. Every v that is unvisited and has residual[u][v] > 0 is added to the queue, has its parent recorded as u, and is immediately marked visited.

It matters that the mark is set when the vertex is added to the queue. If the vertex were marked when it leaves the queue, the same vertex could enter the queue from several different parents. The parent value would also change with the last parent to add it, and the BFS tree would be corrupted. Marking early ensures that every vertex enters the queue exactly once and through its parent closest to the source.

The method returns visited[sink]: if the sink was reached, an augmenting path exists. The parent array holds the BFS tree; following it from the sink to the source gives the path with the fewest edges. This code does not stop when it reaches the sink but continues until the queue is empty. The result does not change, because the sink's parent was written when it was first reached; stopping early only saves a little time. With an adjacency matrix one BFS takes O(V²), with an adjacency list O(V + E).

The main loop is as follows:

int edmondsKarp(int s, int t) {
  int maxFlow = 0;
  int[] parent = new int[V];
  while (bfs(s, t, parent)) {
    int flow = Integer.MAX_VALUE;
    for (int v = t; v != s; v = parent[v])
      flow = Math.min(flow, residual[parent[v]][v]);
    for (int v = t; v != s; v = parent[v]) {
      int u = parent[v];
      residual[u][v] -= flow;  // forward
      residual[v][u] += flow;  // backward
    }
    maxFlow += flow;
  }
  return maxFlow;
}

The condition while (bfs(s, t, parent)) runs a new BFS in every round. The first for loop walks from the sink toward the source. parent[v] is the previous vertex on the path; residual[parent[v]][v] is the residual capacity of that edge. flow falls to the smallest of these values. Its initial value is Integer.MAX_VALUE, so the first comparison always takes the value of a real edge. The second loop walks the same path once more: flow is subtracted from the forward residual capacity and added to the backward residual capacity. At the end of the round maxFlow grows. When BFS cannot reach the sink, the loop ends and the result is returned.

The memory use is O(V²) for the residual matrix and O(V) for parent, visited, and the queue. A matrix is wasteful for sparse networks. For large sparse networks an adjacency list is used, with each edge holding a link to its backward edge; the Java code of Dinic's algorithm uses this representation.

8.5.4Code trace: bfs(s, t, parent)

Let us trace BFS on the network of Figure 8.17. This network is the classic example from the book by Cormen and colleagues. The vertices s, 1, 2, 3, 4, t are numbered 0 to 5 in this order; the loop tries neighbors in this order. Initially all flows are zero and the residual capacity equals the capacity.

1613104129147204s1324t
Figure 8.17: The trace network. Capacities: s→1 16, s→2 13, 1→2 10, 2→1 4, 1→3 12, 3→2 9, 2→4 14, 4→3 7, 3→t 20, 4→t 4.
Table 8.5: The first call bfs(s, t, parent). Each row is the removal of one vertex from the queue.
Extracted uNeighbors added (residual)SkippedQueue
—start: visited[s] = true, parent[s] = −1—[s]
s1 (16), 2 (13); parent s—[1, 2]
13 (12); parent 12 visited[2, 3]
24 (14); parent 21 visited[3, 4]
3t (20); parent 32 visited[4, t]
4—3 and t visited[t]
t—no outgoing residual edge with positive capacity[ ]

The sink is visited when 3 leaves the queue. The code nevertheless continues until the queue is empty. When the loop ends, the parent array is [−1, s, s, 1, 2, 3]. Read back from the sink, the path is s → 1 → 3 → t: only 3 edges. There is no s–t path shorter than 3 in this network; BFS has found the augmenting path with the fewest edges. The bottleneck is min(16, 12, 20) = 12.

1613104129147204s1234tqueuesred: BFS tree (parent) 1613104129147204s1234tqueuered: BFS tree (parent)
Figure 8.18: The beginning and the end of the BFS. (a) Only s is in the queue. (b) The queue is empty; the red edges are the BFS tree (the parent relation). The branch leading to the sink is s → 1 → 3 → t.

8.5.5Code trace: edmondsKarp(s, t)

The whole main loop can be seen in Table 8.6. For each round the path found, the bottleneck, and the updated residual capacities are given.

Table 8.6: Trace of edmondsKarp(s, t).
RoundBFS pathResidual capacitiesflowUpdated cellsmaxFlow
1s→1→3→t (3 edges)16, 12, 2012s→1: 4, 1→3: 0, 3→t: 8; backward: 1→s 12, 3→1 12, t→3 1212
2s→2→4→t (3 edges)13, 14, 44s→2: 9, 2→4: 10, 4→t: 0; backward: 2→s 4, 4→2 4, t→4 416
3s→2→4→3→t (4 edges)9, 10, 7, 87s→2: 2, 2→4: 3, 4→3: 0, 3→t: 1; backward edges grow23
4none——BFS cannot reach t23

The path lengths are 3, 3, and 4; they do not decrease. This is a small example of the first observation in the complexity proof of Edmonds-Karp. After the second round 4 → t is saturated. In the third round one cannot go from 4 directly to the sink; BFS finds the path that goes from 4 to 3 and is one edge longer. The bottleneck is 7, the capacity of 4 → 3.

In the fourth BFS one can go from the source to 1 (residual 4) and to 2 (residual 2). The edge from 1 to 3 is saturated. From 2 one can send 3 units to 4, but both exits of 4 (4 → 3 and 4 → t) are full. Neither 3 nor the sink can be reached; the reachable set is {s, 1, 2, 4}. The method returns 23. The algorithm has made 3 augmentations and 4 BFS runs.

8.5.6Example: the final flow and the minimum cut

Let us use cuts to verify why the flow stops at 23 in the same network. Even before the algorithm starts there is a simple upper bound. The capacity leaving the source is 16 + 13 = 29, and the capacity entering the sink is 20 + 4 = 24. Taking the smaller, |f*| ≤ 24. The value found is 23, one below this bound. The bottleneck is neither at the source nor at the sink; it is in the middle of the network.

41221110412931171194s1324t 12/1611/130/100/412/120/911/147/719/204/4s1324t|f| = 23
Figure 8.19: (a) The final residual network; the vertices reached from the source, s, 1, 2, 4, are highlighted. (b) The final flow and the minimum cut: the T side is {3, t} (red). The cut capacity is 12 + 7 + 4 = 23.
Example 8.5

In the final residual network the set reachable from the source is S = {s, 1, 2, 4}, and the remaining set is T = {3, t}. The original edges going from S to T are:

  • 1 → 3: capacity 12, flow 12 (full).
  • 4 → 3: capacity 7, flow 7 (full).
  • 4 → t: capacity 4, flow 4 (full).

The only edge going from T to S is 3 → 2, and its flow is 0. The cut capacity is 12 + 7 + 4 = 23, equal to the value of the flow. Check from the sink side: the flow into t is 19 + 4 = 23. The flow is maximum. It cannot be enlarged unless the capacity of one of the cut edges is increased.

It is also instructive to look at how the final flow is distributed over the edges. There is no flow on the edges 1 → 2 and 2 → 1; these two edges are not used at all in this solution. There are 12 units on s → 1 and 11 on s → 2. Even though spare capacity remains on the source edges, the flow cannot be increased, because the cut edges are full.

8.5.7Example 2: the A–G network

The second example is a network in which BFS has to find long paths and uses a backward edge. The source is A and the sink is G. BFS tries neighbors in alphabetical order.

33431226119ABCDEFG
Figure 8.20: The A–G network. Capacities: A→B 3, A→D 3, B→C 4, C→A 3, C→D 1, C→E 2, D→E 2, D→F 6, E→B 1, E→G 1, F→G 9.
Table 8.7: Augmenting paths found by Edmonds-Karp in the A–G network.
RoundPathEdgeBottleneckFlow
1A→D→E→G3E→G (1)1
2A→D→F→G3A→D (2 left)3
3A→B→C→D→F→G5C→D (1)4
4A→B→C→E→D→F→G6backward edge E→D (1)5

In the first round BFS puts B and D from A into the queue, C from B, and E and F from D. E leaves the queue before F and is the first to find G. The path is A → D → E → G; since the capacity of E → G is 1, it carries only 1 unit. In the second round E → G is full. BFS finds A → D → F → G; 2 units are left on A → D. The flow becomes 3 and A → D is saturated.

In the third round the source can reach only B. The path stretches to five edges: A → B → C → D → F → G. The bottleneck is C → D (1). The fourth round is the most interesting one. C → D is saturated; the search goes from C to E. There is no direct path from E to the sink, but in the first round 1 unit was sent along D → E. The residual network now has the backward edge E → D, and the path uses it: A → B → C → E → D → F → G.

2133131211331163ABCDEFG 2/33/32/40/31/11/20/24/60/11/14/9ABCDEFG|f| = 5
Figure 8.21: (a) The augmenting path of the fourth round; E → D is a backward edge. (b) The final flow: |f| = 5. The flow on D → E has dropped from 1 to 0.

The effect of the backward edge is this: the unit that in the first round passed from D to E and reached the sink along E → G now comes from C. The unit freed at D reaches the sink along D → F → G. In the final flow the edge D → E is empty. The path lengths are 3, 3, 5, and 6; again they do not decrease.

The fifth BFS cannot reach the sink. From the source, the vertices A, B, C, E are reached. The original edges leaving this set are A → D (3), C → D (1), and E → G (1). The cut capacity is 3 + 1 + 1 = 5 = |f*|. The edge D → E crosses the cut in the opposite direction and is empty in the final flow; the condition in the proof is again satisfied.

8.5.8Example 3: on the residual network

In the third example the algorithm is followed directly on the residual network. One can see step by step how each augmentation changes the residual network.

424213113s1234t
Figure 8.22: The third example network. Capacities: s→1 4, s→4 2, 1→2 4, 1→3 2, 3→2 1, 2→t 3, 3→t 1, 4→3 1, 4→t 3.

At the start the residual network equals the capacities. BFS first finds the two-edge path s → 4 → t. The bottleneck is s → 4 (2); 2 units are pushed. The residual capacity of s → 4 drops to 0, and the backward edge 4 → s becomes 2. 1 unit is left on 4 → t.

Now there is no two-edge path. BFS finds the three-edge path s → 1 → 2 → t; the bottleneck is 2 → t (3). 3 units are pushed. 1 unit is left on s → 1 and on 1 → 2; 2 → t becomes saturated. In the next BFS the sink cannot be reached from 2. The path s → 1 → 3 → t is found; since 1 unit is left on s → 1, 1 unit is pushed.

4/42/23/41/20/13/31/10/12/3s1234t|f| = 6 421311131112s1234t
Figure 8.23: (a) The final flow (flow/capacity). (b) The final residual network: both edges leaving s are saturated, and nowhere can be reached from the source.

The edges leaving the source are saturated; no augmenting path is left. The maximum flow is |f*| = 2 + 3 + 1 = 6: 3 units go along s → 1 → 2 → t, 1 unit along s → 1 → 3 → t, and 2 units along s → 4 → t. The minimum cut is ({s}, the rest), and its capacity is 4 + 2 = 6. In this network the set {s, 1, 2, 3} also gives a cut of capacity 6; once again the minimum cut is not unique.

In this example no path used a backward edge. Some edges were never filled either: 3 → 2 and 4 → 3 stay empty, and there is 1 unit of spare room on 4 → t. A maximum flow does not fill every edge; it fills only the edges of a minimum cut.

8.6Dinic's algorithm

Edmonds-Karp processes a single path after each BFS. Yet the information BFS finds is far richer than a single path: it gives the distance from the source to every vertex. Using these distances, all the shortest paths of the same length can be saturated in a single stage. Yefim Dinitz used this idea in the algorithm he published in 1970; the algorithm is known in the Western literature as Dinic's algorithm.

8.6.1The level graph and the blocking flow

Definition 8.6

A BFS from the source in the residual network gives the level of every vertex v: level(v) is the number of edges on the shortest residual path from the source to v. The level graph is the subgraph of the residual network consisting only of the edges (u, v) that satisfy level(v) = level(u) + 1.

A flow in the level graph that leaves at least one saturated edge on every s–t path is called a blocking flow.

In the level graph every edge goes forward by one level. Edges between vertices of the same level, and edges that go backward, are discarded. Therefore every s–t path in the level graph is one of the shortest s–t paths in the residual network. Moreover the level graph is acyclic: the level increases at every step, so one cannot return to the same vertex.

sabcdtlvl 0lvl 1lvl 2lvl 3
Figure 8.24: The level graph. The vertices are arranged in columns by their distance from the source (lvl 0, 1, 2, 3). Only edges going to the next column are kept; the edges a → b and d → c within a column (faded) are not used.

A blocking flow is not a maximum flow. It only blocks all the paths in the level graph; no s–t path is left in the level graph. But in the whole residual network, longer augmenting paths may remain through edges that do not skip a level and through newly created backward edges. This is why Dinic works in phases: in each phase it recomputes the levels and finds a new blocking flow.

8.6.2The steps of the algorithm

  1. Initialization. The flow on all edges is 0; the residual network is the same as the original network.
  2. BFS. A BFS from the source determines the level of every vertex. BFS uses only edges with positive residual capacity. If the sink has no level, that is, if the sink cannot be reached, the flow is maximum and the algorithm stops.
  3. DFS. Augmenting paths that go forward by one level at each step are searched for with DFS. Only edges with level(v) = level(u) + 1 are followed. Edges found to be dead ends are not tried again during that phase.
  4. Update. The smallest residual capacity on each path found is added to the total flow; the residual capacities of the edges and their backward edges are updated. When no path remains, the blocking flow of this phase has been found.
  5. New phase. Return to step 2.

In every phase the distance from the source to the sink grows by at least 1. Since the distance can be at most V − 1, there are at most V − 1 phases. This is the first factor in the algorithm's running-time bound.

8.6.3Example: the phases

Let us run the algorithm on the network of Figure 8.25. This network is the same as that of the second Ford-Fulkerson example; only the names of vertices 2 and 3 are swapped. We therefore know that the maximum flow is 19.

0/100/100/40/20/80/90/60/100/10s1324t|f| = 0
Figure 8.25: The Dinic example network (flow/capacity); initially all flows are 0. Capacities: s→1 10, s→2 10, 1→2 2, 1→3 4, 1→4 8, 2→4 9, 4→3 6, 3→t 10, 4→t 10.

Phase 1, BFS. Levels: s = 0; 1, 2 = 1; 3, 4 = 2; t = 3. The edge 1 → 2 joins two level-1 vertices, and the edge 4 → 3 joins two level-2 vertices. Neither skips a level, and neither is used in this phase. The distance from the source to the sink is 3.

Phase 1, blocking flow. DFS finds three paths in the level graph: {s, 1, 3, t} with 4 units (the capacity of 1 → 3), {s, 1, 4, t} with 6 units (what is left on s → 1), and {s, 2, 4, t} with 4 units (what is left on 4 → t). The total is |f| = 14. After this phase no s–t path is left in the level graph: s → 1, 1 → 3, and 4 → t are saturated.

1010428961010s1324t012123 10/104/104/40/26/84/90/64/1010/10s1324t|f| = 14
Figure 8.26: The first phase. (a) The level graph; the blue numbers next to the vertices are levels, and the faded edges skip no level. (b) The flow after the blocking flow; |f| = 14.

Phase 2, BFS. In the residual network the source can reach only 2 (6 units remain on s → 2). From 2, 5 units can go to 4. From 4 one can go in two directions: the edge 4 → 3 and the backward edge 4 → 1 of the flow sent to 1 → 4 in the first phase. From 3 one also reaches the sink. The levels are s = 0; 2 = 1; 4 = 2; 1, 3 = 3; t = 4. The distance from the source to the sink has risen from 3 to 4.

Phase 2, blocking flow. DFS first descends from 4 to 1. Vertex 1 has no edge to a vertex at level 4; the edge 4 → 1 is a dead end. DFS abandons this edge and continues with 4 → 3 → t. The path is {s, 2, 4, 3, t}, and the bottleneck is 2 → 4 (9 − 4 = 5). |f| = 14 + 5 = 19.

106442265466410s1324t033124 101942269151910s1324t0∞∞1∞∞
Figure 8.27: (a) The level graph of the second phase; the dashed edges are backward edges of the first phase. (b) The third BFS: from the source only 2 is reached, and the sink has no level (∞).

Phase 3, BFS. In the residual network only 2 is reached from the source (1 unit remains on s → 2); 2 → 4 is saturated. The sink has no level, and the algorithm ends. The minimum cut is ({s, 2}, the rest): s → 1 (10) + 2 → 4 (9) = 19.

Result: the maximum flow is 19, and only 2 phases, that is, 2 + 1 = 3 BFS runs, were enough. On the same network the second Ford-Fulkerson example used 5 augmenting paths. Edmonds-Karp makes 4 augmentations and 5 BFS runs on this network. Dinic's gain comes from processing the three paths of length 3 in the first phase with the information of a single BFS.

8.6.4Pseudocode

The main loop and the BFS of Dinic's algorithm are below.

DINIC(G, source, sink):
  flow = [ ]       // 0 for every edge
  maxFlow = 0
  while BFS(G, source, sink, flow):
    // level graph built
    while a blocking flow remains:
      delta = DFS(G, source, sink,
                  flow, level, ∞)
      maxFlow += delta
  return maxFlow

BFS(G, source, sink, flow):
  level[v] = −1, for each v
  level[source] = 0
  queue.add(source)
  while queue is not empty:
    u = queue.remove()
    for each (u, v) in G[u]:
      if level[v] < 0 and
           capacity[u,v] − flow[u,v] > 0:
        level[v] = level[u] + 1
        queue.add(v)
  return level[sink] ≥ 0

The outer loop runs as long as BFS reaches the sink; each round is a phase. The inner loop calls DFS again and again until the blocking flow is complete. Each DFS finds a path and returns the flow of that path; when it returns 0 the phase ends. The BFS is very similar to the BFS in Edmonds-Karp. The difference is that the level is recorded instead of the parent. The level of unreached vertices is −1. BFS returns true if the level of the sink is not negative.

DFS(G, u, sink, flow, level, limit):
  if u == sink: return limit
  for each (u, v) in G[u]:
    remaining = capacity[u,v] − flow[u,v]
    if level[v] == level[u] + 1
         and remaining > 0:
      delta = DFS(G, v, sink, flow, level,
                  min(limit, remaining))
      if delta > 0:
        flow[u, v] += delta
        flow[v, u] −= delta   // backward
        return delta
  return 0

The limit parameter of DFS is the bottleneck of the path from the source to u. It starts at ∞ at the source and shrinks at every edge to min(limit, remaining). When the sink is reached this value is returned; it is the bottleneck of this path. On the way back each edge increases its flow by delta and the flow of the backward edge decreases. The level condition (level[v] == level[u] + 1) ensures that the search advances only in the level graph.

8.6.5Java: level-based DFS and the current-arc array

The DFS in the pseudocode tries all edges from the beginning on every call. Even when an edge is known to be a dead end, it is tried again on the next call. This needlessly lengthens the phase. The Java implementation avoids this with a small array:

int dfs(int u, int t, int pushed, int[] ptr) {
  if (u == t) return pushed;
  for (; ptr[u] < adj[u].size(); ptr[u]++) {
    Edge e = adj[u].get(ptr[u]);
    if (level[e.to] == level[u] + 1 && e.flow < e.cap) {
      int d = dfs(e.to, t, Math.min(pushed, e.cap - e.flow), ptr);
      if (d > 0) {
        e.flow += d;                           // forward edge
        adj[e.to].get(e.rev).flow -= d;        // backward edge
        return d;
      }
    }
  }
  return 0;   // no level path left from u to t
}

The edges are kept in adjacency lists. Each Edge object carries the target vertex, the capacity, the flow, and a rev field. rev is the position of the reverse edge in the target vertex's list. So the expression adj[e.to].get(e.rev) reaches the reverse edge in O(1). When an edge is added, two objects are created together: the forward edge with its capacity and the backward edge with capacity 0.

ptr[u] is the index of the next edge to try at u; this structure is called the current arc. The for loop starts at ptr[u], and the counter is incremented directly in this array. If no flow reaches the sink through an edge (d == 0), the loop moves on to the next edge with ptr[u]++, and this edge is never tried again during that phase. If flow does reach the sink, the method returns without incrementing ptr[u]. The edge may still have room; the next call starts from the same edge.

The condition e.flow < e.cap says that the residual capacity is positive. For backward edges the capacity is 0 and the flow is negative: −f. The condition becomes −f < 0, that is, f > 0, and the residual capacity comes out as 0 − (−f) = f. Forward and backward edges are handled by the same line. At the start of every phase the ptr array is reset and the levels are recomputed by BFS.

Common mistake

Incrementing ptr[u] in every case. When flow gets through, the edge may not be saturated; if the counter is incremented, the remaining capacity of the edge goes unused in that phase. The algorithm still gives the correct result, but the blocking flow is left incomplete and the number of phases grows. Conversely, if the counter is never used, dead-end edges are tried again and again and the per-phase bound of O(V · E) is lost.

8.6.6Code trace: the blocking flow in the first phase

Let us trace the DFS calls of the first phase. In the adjacency lists the edges are in the order they were added: in the list of 1, after the backward edge from s come 1 → 2, 1 → 3, and 1 → 4; in the list of 4, after two backward edges come 4 → 3 and 4 → t. Backward edges do not satisfy the level condition in this phase.

Table 8.8: The calls dfs(s, t, ∞, ptr) in the first phase.
CallPath descended (remaining)EventReturned d|f|
1s→1 (10), 1→3 (4), 3→t (10)1 → 2 is at the same level, ptr[1]++. The flow is limited to min(10, 4, 10) = 4.44
2s→1 (6), 1→4 (8), 4→t (10)1 → 3 is saturated, ptr[1]++. At 4, 4 → 3 is at the same level, ptr[4]++.610
3s→2 (10), 2→4 (9), 4→t (4)s → 1 is saturated, ptr[s]++. 4 units remain on 4 → t.414
4s→2 (6), 2→4 (5)At 4, 4 → t is saturated, ptr[4]++; the list is finished: 0. At 2, ptr[2]++: 0. At s, ptr[s]++: 0.014

The fourth call shows that the blocking flow is complete. In this call no level path is left from 4: 4 → 3 is at the same level and 4 → t is saturated. As the value 0 is passed upward, every vertex advances its counter. Finally ptr[s] reaches the end of the list and the phase ends with |f| = 14.

4/100/104/40/20/80/90/64/100/10slvl 01lvl 12lvl 13lvl 24lvl 2tlvl 3calls: dfs(s, ∞) 10/104/104/40/26/84/90/64/1010/10slvl 01lvl 12lvl 13lvl 24lvl 2tlvl 3calls: dfs(s, ∞) → dfs(2, 6) → dfs(4, 5)
Figure 8.28: Two moments of the level-based DFS. (a) As the flow of the first path returns, 4 is added to each edge; |f| = 4. (b) The fourth call: the descent went along s → 2 → 4, and no level path is left from 4.

In the table the total number of increments of the ptr counters is small: each edge is declared a “dead end” at most once during a phase. This is the value of the current-arc array. Since a dead-end edge is never looked at again, the total work of all the DFS calls in a phase stays bounded.

8.6.7Complexity: O(V² · E)

Theorem 8.6 (Dinic)

Dinic's algorithm makes at most V − 1 phases. With the current-arc array each phase takes O(V · E). The total time is O(V² · E).

Number of phases. At the end of a phase every s–t path in the level graph contains a saturated edge. The new edges in the residual network of the next phase are only backward edges, and these go back one level in the level graph. An s–t path of the same length as before could consist only of edges of the level graph; all of these paths are blocked. So the distance from the source to the sink strictly increases. Since the distance lies between 1 and V − 1, there are at most V − 1 phases.

Time per phase. BFS takes O(V + E). The work of the DFS runs splits into two parts. Each successful DFS follows a path of at most V − 1 edges and saturates at least one edge on it. A saturated edge is not used again in that phase; so there are at most E successful DFS runs, and their total cost is O(V · E). In unsuccessful attempts the counter advances one step; at most once per edge, O(E) in total. Per phase, O(V · E).

Total: O(V) · O(V · E) = O(V² · E). □

Comparing Dinic's bound with Edmonds-Karp's makes the gain clear. In networks with E ≥ V we have V² · E ≤ V · E²; the gap grows as the network gets denser. For V = 1000 and E = 10,000, the value of V · E² is 1011 and the value of V² · E is 1010.

In special networks the bound is even better. If all capacities are 1, the number of phases is bounded by O(√E) and each phase takes O(E): in total O(E · √E). In unit networks, such as bipartite matching, where at most one unit of flow passes through each vertex, the time drops to O(E · √V). This is the bound of the Hopcroft-Karp algorithm; Hopcroft-Karp is in fact a form of Dinic's algorithm adapted to matching.

In practice Dinic's algorithm is the maximum-flow algorithm most used in competitive programming. Its code is short and it usually runs far below its bound. In most networks the number of phases is far smaller than V; in the example of these notes 2 phases were enough.

8.7Push–relabel

8.7.1The idea: letting water run downhill

All the algorithms so far work globally: at every step they look for a complete path from the source to the sink. The push–relabel algorithm, published by A. Goldberg and R. Tarjan in 1988, takes a completely different route. It does not search for augmenting paths. Each operation concerns a single vertex and its neighbors; the algorithm reaches the maximum flow by repeating these local operations.

It helps to think of the algorithm as a water system. At the start, all the pipes leaving the source are filled to the brim. The water collects at the source's neighbors. Every vertex has a height, and water flows only from a higher vertex to a lower one. A vertex that cannot pass its accumulated water to any neighbor is raised; this is called a relabel. Passing water to a neighbor is called a push. Excess water that cannot reach the sink returns to the source once its height exceeds the height of the source. When no vertex holds any accumulated water, the water that has reached the sink is the maximum flow.

h=0h=1h=2h=3h=4suvtsaturated at startpushh(v) = h(t): cannot push → relabel
Figure 8.29: The idea of push–relabel. The source is at height h = 4 and its edges are saturated at the start. u (h = 1) pushes its excess to a lower neighbor (v, h = 0). Since v and t are at the same height, v cannot push to the sink; it must be relabeled first.

8.7.2Preflow and excess flow

The structure in the intermediate steps of the algorithm is not a flow; the conservation constraint is violated. More water may enter a vertex than leaves it. This relaxed structure is called a preflow.

Definition 8.7

A preflow is a function f that obeys the capacity constraint and, in place of conservation, satisfies the following condition: for every vertex v other than the source,

e(v) = Σu f(u, v) − Σw f(v, w) ≥ 0

e(v) is called the excess flow of v: the total flow in minus the total flow out. A vertex other than the source and sink with e(v) > 0 is an active vertex.

3724u₁u₂Vw₁w₂
Figure 8.30: Vertex V receives 3 units from u1 and 7 from u2; 2 units leave V toward w1 and 4 toward w2. The excess is e(V) = (3 + 7) − (2 + 4) = 4.

In a preflow, conservation is relaxed in only one direction: a vertex can accumulate flow, but it cannot give away flow it does not have. The excess is never negative. Conservation means that e(v) = 0 at all intermediate vertices. So when no active vertex remains, the preflow has become a true flow. The algorithm runs until that moment.

8.7.3The height function and initialization

The algorithm assigns each vertex an integer h(v). The initialization is as follows:

  • The flow on all edges is 0.
  • h(s) = |V|, the number of vertices; all other vertices have h = 0.
  • Every edge leaving the source is saturated: f(s, v) = c(s, v) and e(v) = c(s, v).

Two invariants are maintained throughout the algorithm. First, h(s) = |V| and h(t) = 0 never change; the source and the sink are not relabeled. Second, for every edge (u, v) in the residual network, h(u) ≤ h(v) + 1. This second invariant says that the height can drop by at most 1 along an edge. Slopes cannot be steep.

The second invariant has an important consequence: h(u) is a lower bound on the residual-network distance from u to the sink. If there is a residual path with k edges from u to the sink, the height drops by at most 1 on each edge; since the height of the sink is 0, h(u) ≤ k.

Theorem 8.7 (No s–t path)

As long as the invariants hold, there is no path from the source to the sink in the residual network. Hence, if the algorithm stops when no active vertex remains, the flow obtained is maximum.

If there were a path from the source to the sink in the residual network, as a simple path it would have at most |V| − 1 edges. By the observation just made, we would need h(s) ≤ |V| − 1. But h(s) = |V|. A contradiction. When no active vertex remains, the preflow is a flow and its residual network has no augmenting path; by the max-flow min-cut theorem it is a maximum flow. □

This viewpoint shows that the algorithm works the other way around from the Ford-Fulkerson family. Ford-Fulkerson maintains a valid flow at every moment and runs until no augmenting path is left. Push–relabel maintains the condition “no augmenting path” at every moment and runs until the preflow is a valid flow. The initial value h(s) = |V| establishes this condition. Because the edges leaving the source are saturated, no edge leaves the source in the residual network; the invariant holds at the start as well.

8.7.4The push and relabel operations

Push: push(u, v). The condition has three parts: e(u) > 0; cf(u, v) > 0, that is, the edge has a gap between capacity and flow; and h(u) = h(v) + 1. Under these conditions δ = min(e(u), cf(u, v)) units of flow are pushed: f(u, v) increases (or f(v, u) decreases if it is a backward edge), e(u) −= δ, e(v) += δ. If the push saturates the edge it is called a saturating push, otherwise a non-saturating push. In a non-saturating push, δ = e(u) and the excess of u is emptied completely.

Relabel: relabel(u). The condition: e(u) > 0, but h(u) ≤ h(v) for every edge (u, v) in the residual network; that is, it cannot push to any neighbor. The operation is h(u) = 1 + min h(v), with the minimum taken over the edges (u, v) in the residual network. With this new value at least one push becomes possible: the lowest neighbor is exactly one step below.

Both operations preserve the invariants. A push is made only on an edge with h(u) = h(v) + 1. On the backward edge (v, u) that may be created, h(v) = h(u) − 1 ≤ h(u) + 1; the invariant holds. In a relabel, h(u) is chosen exactly one more than the smallest of its residual neighbors; the invariant is preserved on the edges leaving u. On the edges entering u, an increase of h(u) only relaxes the condition.

Flow is pushed from high to low, and heights only increase. A vertex with excess flow always has a path to the source in the residual network: this flow came from the source along some path, and the backward edges of that path are in the residual network. So the min in the relabel is always defined. Excess that cannot reach the sink is pushed back toward the source once it rises above |V|, the height of the source.

Common mistake

Mixing up the direction of the push or the initial height. Flow is pushed only from high to low, when h(u) = h(v) + 1. Pushing to a neighbor of equal height breaks the invariant. At the start h(s) = |V| must hold; if the source is left at 0, the excess cannot return to the source and the “no augmenting path” guarantee is lost.

8.7.5Example: step by step

The network in Figure 8.31 has six vertices: |V| = 6. Active vertices may be chosen in any order; the order in the example was chosen to show the operations clearly.

0/130/100/30/60/70/100/5sABCDt 13/1310/100/30/60/70/100/5sABCDt
Figure 8.31: (a) The push–relabel example network (flow/capacity): s→A 13, s→B 10, B→A 3, A→C 6, A→t 7, C→D 10, D→t 5. (b) Start: h(s) = 6, the two edges of the source are saturated; e(A) = 13, e(B) = 10.
Table 8.9: Trace of push–relabel. The heights (h) and excess flows (e) after each row; h(s) = 6 and h(t) = 0 do not change.
StepOperationA (h, e)B (h, e)C (h, e)D (h, e)e(t)
0start: s → A and s → B are saturated0, 130, 100, 00, 00
1relabel(B): 1 + min(h(A) = 0, h(s) = 6)0, 131, 100, 00, 00
2push(B, A): δ = min(10, 3) = 30, 161, 70, 00, 00
3relabel(A): 1 + min(0, 0, 1, 6)1, 161, 70, 00, 00
4push(A, C) 6, push(A, t) 7 (both saturate)1, 31, 70, 60, 07
5relabel(C): 1 + h(D)1, 31, 71, 60, 07
6relabel(A): neighbors B (1), s (6)2, 31, 71, 60, 07
7push(A, B) 3 (cancels the flow on B → A)2, 01, 101, 60, 07
8relabel(B) → 3, push(B, A) 32, 33, 71, 60, 07
9Alternating relabel and push between A and B: h(A) = 4, h(B) = 5, h(A) = 6, h(B) = 7; B pushes 3 units to A and 7 units to the source6, 37, 01, 60, 07
10relabel(A): 1 + min(6, 7) = 7; push(A, s) 37, 07, 01, 60, 07
11push(C, D) 67, 07, 01, 00, 67
12relabel(D) → 1, push(D, t) 57, 07, 01, 01, 112
13relabel(D) → 2, push(D, C) 17, 07, 01, 12, 012
14Alternating relabel and push between C and D: C 3, 5, 7, 8; D 4, 6, 8; C pushes 1 unit to A7, 17, 08, 08, 012
15push(A, s) 17, 07, 08, 08, 012

The first steps show the conditions of the operations. In the first step B is active, but of its residual neighbors A is at the same height (0); the source is far higher. B cannot push and is relabeled. It then looks at A from one step above and pushes 3 units, the capacity of the edge B → A. In the third step the neighbors of A are C (0), t (0), B (1; the backward edge of the flow B → A), and s (6; the backward edge of the flow s → A). The smallest is 0, and h(A) = 1.

In the fourth step A distributes its excess to the sink and to C. The edge to the sink saturates at 7 and the edge of C at 6. 3 units remain at A. These 3 units have no way to reach the sink: both exits of A are full. Most of the following steps are this excess returning to the source.

13/1310/103/36/67/70/100/5sABCDt
Figure 8.32: The fourth step: A pushes 6 units to C and 7 to the sink. Both edges saturate; e(A) = 3, e(C) = 6, and 7 at the sink.

The part from the sixth step to the ninth shows the most criticized aspect of the algorithm. A and B push the excess back and forth; each time one of them rises a step. This “playing catch” continues until both heights exceed 6, the height of the source. When h(B) = 7, B is higher than the source. Of the 10 units of excess at B, 3 go to A and 7 go to the source (the flow on s → B drops from 10 to 3). In the tenth step A also rises to 7 and pushes its own 3 units to the source.

In the following steps the same thing happens between C and D. The 6 units of C go to D; D pushes 5 of them to the sink, because the capacity of D → t is 5. The remaining 1 unit goes back and forth between C and D. When the heights exceed 7, the height of A, C pushes this unit to A (the flow on A → C drops from 6 to 5); A then pushes it to the source.

13/133/103/36/67/70/100/5sABCDt 9/133/103/35/67/75/105/5sABCDt
Figure 8.33: (a) The ninth step: the excess of B has returned to the source; the flow s → B has dropped to 3. (b) The final state: no active vertex. s → A 9, s → B 3; the flow into the sink is 12.

When no active vertex remains, the maximum flow is the flow into the sink: 7 + 5 = 12. The flow out of the source is also 9 + 3 = 12. The minimum cut is S = {s, A, B, C, D}, T = {t}: A → t (7) + D → t (5) = 12.

The order of selection in the example is not the only option. The Java functions on the slides can also be run with a main loop that picks the first active vertex in index order each time. On the same network this loop performs 38 operations (relabels and pushes) and again finds 12. The order changes the number of operations, not the result.

8.7.6Pseudocode

The initialization part of the algorithm is as follows:

PUSH_RELABEL(G, source, sink):
  height[source] = |V|
  height[v] = 0, v ≠ source
  excess[v] = 0, for each v
  flow[e] = 0, for each edge e
  // preflow: saturate the source edges
  for each (source, v) ∈ E:
    c = capacity[source, v]
    flow[source, v] = c
    flow[v, source] = −c
    excess[v] = c
    excess[source] −= c

The flow is kept in a skew-symmetric table: when a source edge is saturated, flow[v, source] = −c is written. The excess of the source becomes negative; the source is a special vertex in this respect. The main loop is as follows:

while some u has excess[u] > 0:
  // u ≠ source, u ≠ sink
  if residual(u,v) > 0 and
       height[u] == height[v]+1:
    // push
    delta = min(excess[u], residual(u,v))
    flow[u,v] += delta
    flow[v,u] −= delta
    excess[u] −= delta
    excess[v] += delta
  else:
    // relabel
    m = ∞
    for each (u, v) in G[u]:
      if flow[u,v] < capacity[u,v]:
        m = min(m, height[v])
    height[u] = m + 1
return excess[sink]
// residual = capacity − flow

The loop runs as long as an active vertex u is found. If the push condition holds for some neighbor v of u, a push is made; if not, u is relabeled. The relabel part finds the smallest height among the neighbors in the residual network, that is, among the edges with flow < capacity, and writes one more than it. When the loop ends, the excess of the sink is returned; this is the total flow that has reached the sink.

8.7.7Java: push() and relabel()

In the Java implementation each Node object holds its own height and excess fields and the list of its outgoing edges. The push operation is as follows:

boolean push(Node n) {
  for (Edge e : n.edges) {
    if (n.height > e.to.height
        && e.flow != e.cap) {
      int flow = Math.min(
        e.cap - e.flow, n.excess);
      n.excess -= flow;
      e.to.excess += flow;
      e.flow += flow;
      updateReverse(e, flow);
      return true;   // pushed
    }
  }
  return false;
}

The method tries the edges of the vertex in order. The expression n.height > e.to.height in the condition looks looser than the theoretical condition h(u) = h(v) + 1. But because of the invariant the two are the same: on an edge in the residual network h(u) ≤ h(v) + 1, so h(u) > h(v) is possible only when h(u) = h(v) + 1. e.flow != e.cap says that the edge is in the residual network.

When the condition holds, the amount pushed is the smaller of the residual capacity and the excess. The vertex's excess decreases, that of the target vertex increases, the flow on the edge grows, and updateReverse reduces the flow of the backward edge by the same amount. Backward edges are stored as edges with capacity 0 and negative flow. The method returns true after the first successful push. If no edge is suitable it returns false and the vertex is relabeled:

void relabel(Node n) {
  int minH = Integer.MAX_VALUE;
  for (Edge e : n.edges) {
    // only edges in the residual network
    if (e.flow != e.cap
        && e.to.height < minH) {
      minH = e.to.height;
      n.height = minH + 1;
    }
  }
}

The loop finds the lowest among the neighbors in the residual network and sets the height to one more than that. The assignment is made inside the loop, but since the last assignment made corresponds to the smallest height, the result is correct. The main loop combines the two methods: while there is an active vertex, if (!push(n)) relabel(n);. The result is the excess of the sink.

A push takes O(1); a relabel takes time proportional to the degree of the vertex. The code scans the edge list from the start on every call. This is a choice made for simplicity; efficient implementations keep a “next edge” pointer similar to the ptr array in Dinic's algorithm.

8.7.8Complexity

The running time is found by counting how many times each type of operation can be performed. Table 8.10 summarizes the results.

Table 8.10: The total number of push–relabel operations.
OperationTotal countReason
RelabelO(V²)the height of every vertex is ≤ 2|V| − 1 and only increases
Saturating pushO(V · E)for an edge to be saturated again, the heights at both endpoints must rise by ≥ 2
Non-saturating pushO(V² · E)via the potential function Σ h(v) (active v)

Relabels. An active vertex has a path to the source in the residual network. This path has at most |V| − 1 edges, and the height drops by at most 1 on each edge. Hence h(u) ≤ h(s) + |V| − 1 = 2|V| − 1. Since every relabel raises the height by at least 1, a vertex is relabeled at most 2|V| − 1 times; in total O(V²). In our example, for |V| = 6 the bound is 11; the highest label reached was 8.

Saturating pushes. When an edge (u, v) is saturated, h(u) = h(v) + 1. For it to be saturated again in the same direction, a push must first be made from v to u; for that h(v) must rise to h(u) + 1, that is, increase by at least 2. Then u must rise by 2 as well. Since heights cannot exceed 2|V|, each edge is saturated O(V) times; in total O(V · E).

Non-saturating pushes. The sum of the heights of the active vertices, Φ, is used as a potential. A non-saturating push makes u inactive and decreases Φ by at least 1 (even if v becomes active, h(v) = h(u) − 1). Relabels raise Φ by O(V²) in total, and saturating pushes by at most O(V · E) · 2V. Hence the number of non-saturating pushes is O(V² · E).

The generic algorithm takes O(V² · E) in the worst case. A relabel scans at most as many edges as the degree; the total scan is O(V · E) and does not change the dominant term. The rule for choosing the active vertex improves the bound. If the active vertices are kept in a FIFO (first-in first-out) queue, the time drops to O(V³). If the active vertex with the highest label is chosen each time, the time is O(V² · √E).

In practice two heuristics speed the algorithm up a great deal. The gap heuristic notices that no vertex is left at some height value. In that case the vertices above that value cannot reach the sink; the heuristic moves them directly above |V|. The long “playing catch” stretches of the example are shortened to a single step this way. Global relabeling occasionally runs a BFS backward from the sink and sets all heights to the true distances. With these heuristics push–relabel is one of the fastest general-purpose maximum-flow methods.

8.8Comparison and applications

8.8.1Comparing the algorithms

When the four algorithms are run on the same network, the differences become concrete. Table 8.11 summarizes the results on the second example network, whose maximum flow is 19.

Table 8.11: Comparison of the algorithms. The last column is the behavior on the example network with |f*| = 19.
AlgorithmBasic operationTimeOn the example network
Ford-Fulkersonany augmenting path (DFS)O(E · |f*|)5 augmenting paths (the order in Example 2)
Edmonds-Karpshortest augmenting path (BFS)O(V · E²)4 augmenting paths, 5 BFS runs
Diniclevel graph + blocking flowO(V² · E)2 phases, 3 BFS runs
Push–relabellocal push / relabelO(V² · E), FIFO O(V³)searches for no paths

Edmonds-Karp finds these paths in this network: S → 1 → 2 → T (4), S → 1 → 4 → T (6), S → 3 → 4 → T (4), and S → 3 → 4 → 2 → T (5). The first three paths have three edges, the last has four. The fifth BFS cannot reach the sink. Dinic's first phase processes the first three paths after a single BFS; its second phase finds the fourth path.

A rough rule for choosing can be given. If the capacities are small integers, Ford-Fulkerson is enough and is the shortest code. As a general-purpose implementation Dinic is a good default: its code is short, its bound is good, and it is fast in practice. On very large and dense networks push–relabel, together with its heuristics, is usually the fastest. All the algorithms find the same value |f*|. The distribution of the flow over the edges may differ. The minimum cut is in every case read from the final residual network.

8.8.2All the steps on one network

All the concepts introduced in this chapter can be applied together on a small network.

54236243sabcdt
Figure 8.34: The problem network. Capacities: s→a 5, s→b 4, a→b 2, a→c 3, b→d 6, d→c 2, c→t 4, d→t 3.
Example 8.6

Upper bound. The capacity leaving the source is 5 + 4 = 9, and the capacity entering the sink is 4 + 3 = 7. Hence |f*| ≤ 7.

Edmonds-Karp. BFS tries neighbors alphabetically. In the first BFS the queue order is a, b, c, d; c is the first to find the sink. The path is s → a → c → t, with bottleneck 3 (a → c). In the second BFS a → c is full; s → b → d → t is found, with bottleneck 3 (d → t). In the third BFS d → t is full; s → b → d → c → t is found. The bottleneck is min(1, 3, 2, 1) = 1. The first two paths have 3 edges, the last has 4. The total flow is 3 + 3 + 1 = 7.

Minimum cut. In the final residual network there are 2 units on s → a. a → b is empty; 2 units are left on b → d and 1 unit on d → c. Every vertex other than the sink is reachable from the source: S = {s, a, b, c, d}. The cut edges are c → t (4) and d → t (3); the capacity is 7. The flow is maximum.

Residual capacities. cf(s, a) = 5 − 3 = 2. c → d is not an edge of the original network; since there is 1 unit of flow on d → c, cf(c, d) = f(d, c) = 1 (a backward edge).

Start of push–relabel. There are six vertices: h(s) = 6, the others 0. s → a and s → b are saturated: e(a) = 5, e(b) = 4, and the other excesses are 0.

8.8.3Applications

The power of maximum flow comes from the fact that many problems with no apparent connection to flow can be turned into a flow network. After the transformation, any of the algorithms described in this chapter is used.

Bipartite matching. Consider two groups, such as workers and jobs, or students and projects. Each worker is joined by an edge to the jobs he or she can do. Each worker can take at most one job, and each job at most one worker. The goal is the largest possible number of matched pairs. This problem is turned into a flow network as follows: a source is joined to all the workers, and all the jobs are joined to a sink; the worker–job edges stay as they are. All capacities are 1.

sa1a2a3b1b2b3t
Figure 8.35: A bipartite matching network. All edges have unit capacity. The highlighted edges are a maximum matching: a1–b2, a2–b1, a3–b3.

Since the edge from the source to a worker has capacity 1, at most one unit of flow leaves that worker; a worker is assigned to at most one job. The edge from a job to the sink imposes the same limit on jobs. The integrality theorem guarantees that the maximum flow is 0 or 1 on every edge. The worker–job edges that carry flow form a matching, and the value of the flow is the size of the matching. In the network of Figure 8.35, worker a1 can do b1 and b2, a2 can do only b1, and a3 can do b2 and b3. The maximum flow is 3; everyone gets a job.

Edge-disjoint paths. What is the largest number of paths between two vertices that share no edge? This question concerns the robustness of networks: how many links must fail before communication is cut? Every edge is given capacity 1; the maximum flow equals the number of edge-disjoint paths. Menger's theorem says that this number equals the smallest number of edges that must be deleted to separate the two vertices. This is the unit-capacity special case of the max-flow min-cut theorem.

Vertex capacities. In some problems the constraint is on vertices rather than edges: at most a certain number of vehicles can pass through an intersection per hour. Each vertex v is split into two vertices: an input vin and an output vout. An edge vin → vout with capacity c(v) is placed between them. The edges entering v are attached to vin, and those leaving v are attached to vout. All the flow passing through the vertex is forced to use this single edge.

Image segmentation. To separate foreground from background in a photograph, each pixel becomes a vertex. The source stands for “foreground” and the sink for “background.” The probability that a pixel is foreground becomes the capacity of the edge from the source, and the probability that it is background the capacity of the edge to the sink. Edges between neighboring pixels reward keeping similar pixels on the same side. The minimum cut gives the partition that minimizes the total “mislabeling cost.”

Network reliability, transportation, and logistics. The smallest total capacity that must be cut to split a communication network in two is a minimum cut. Maximum flow or minimum cut is also a basic tool in pipelines, traffic planning, airline scheduling, and project selection. In most of these problems the real work is building the right network; the algorithm is ready.

8.9Common mistakes

Most mistakes in network flow problems come from a few confusions of concepts. The list below gathers them.

  • Forgetting backward edges. Searching with forward edges only is a greedy algorithm and may miss the maximum; on the second example network the result is 18 instead of 19.
  • Computing the bottleneck from capacities. The bottleneck is the smallest of the residual capacities, not of the capacities: c − f on a forward edge and f on a backward edge. After the second augmentation some edges are partly full, so looking at capacities gives a wrong and too large bottleneck.
  • Taking the minimum cut to be the one with the fewest edges. A minimum cut cuts the smallest total capacity, not the fewest edges.
  • Counting edges from T to S. Only edges going from S to T enter the cut capacity; backward ones are not added. In computing the net flow across a cut, however, flows in the backward direction are subtracted. The two computations must not be confused.
  • Taking the value of a flow to be the sum of the edge flows. The value is only the net flow leaving the source; the same unit is not counted again on every edge of its path.
  • Treating Ford-Fulkerson as polynomial. O(E · |f*|) depends on the values of the capacities. Edmonds-Karp, which works with BFS, removes this dependence.
  • Measuring “shortest” in Edmonds-Karp by capacity. The shortest path is the one with the fewest edges. Choosing the path of largest capacity is a separate heuristic, and the bound of Edmonds-Karp does not hold for it.
  • Relaxing the level condition in Dinic's algorithm. DFS must follow only edges with level(v) = level(u) + 1. If edges within the same level are allowed, DFS can enter a cycle and the bound on the number of phases becomes invalid.
  • Mixing up the direction of the push. Flow is pushed from high to low, only when h(u) = h(v) + 1; at the start h(s) = |V| must hold.
  • Reading the minimum cut from the wrong residual network. The cut is read from the vertices reachable from the source in the final residual network, after the algorithm has finished. A set read from the residual network of an intermediate step may give a cut, but not necessarily a minimum one.

8.10Summary

  • Flow network: a directed graph of a source, a sink, and edges with capacities. A flow obeys the capacity constraint (0 ≤ f ≤ c) and conservation at intermediate vertices (in = out). The value |f| is the net flow leaving the source. Multiple sources and sinks are reduced to a single-source problem with a supersource and a supersink joined by edges of infinite capacity.
  • Residual network: the residual capacity of a forward edge is c − f and that of a backward edge is f. The backward edge makes it possible to undo flow already sent. An augmenting path is an s–t path in the residual network; the bottleneck is the smallest residual capacity on the path. Augmenting along the path by the bottleneck gives a valid flow and increases its value by the bottleneck.
  • Cut: c(S, T) is the sum of the capacities of the edges going from S to T. The net flow across every cut equals |f|; hence |f| ≤ c(S, T). The maximum flow equals the minimum cut. The S side of the minimum cut is the set of vertices reachable from the source in the final residual network.
  • Ford-Fulkerson: uses any augmenting path. With integer capacities it terminates, finds a flow of integer value, and takes O(E · |f*|). A bad choice of paths can require as many augmentations as the capacity.
  • Edmonds-Karp: chooses the shortest augmenting path with BFS. Distances do not decrease, and each edge becomes critical O(V) times; O(V · E) augmentations and O(V · E²) time.
  • Dinic: in each phase builds a level graph with BFS and finds a blocking flow with DFS and the current-arc array. At most V − 1 phases, O(V · E) per phase; in total O(V² · E). It is much faster on unit capacities.
  • Push–relabel: starts with h(s) = |V| and builds a preflow by saturating the source edges. Flow is pushed from high to low; if it cannot be pushed, the vertex is relabeled. When no active vertex remains, the preflow is a maximum flow. The generic version runs in O(V² · E), the FIFO version in O(V³).
  • Applications: bipartite matching, edge-disjoint paths, networks with vertex capacities, image segmentation, and network reliability are modeled as maximum flow or minimum cut.

8.11Key terms

  • flow network
  • source / sink
  • capacity
  • flow conservation
  • maximum flow
  • residual network
  • residual capacity
  • augmenting path
  • bottleneck
  • cut (s-t cut)
  • max-flow min-cut theorem
  • Ford-Fulkerson method
  • Edmonds-Karp algorithm
  • Dinic's algorithm
  • level graph
  • blocking flow
  • push-relabel
  • excess flow
  • bipartite matching

8.12Test Yourself

  1. In the flow of Figure 8.2, which edges and capacities do the edges B→C (2/3) and C→D (5/6) produce in the residual network? Is there an augmenting path in the residual network for this flow?

    Answer

    B→C: forward cf(B, C) = 3 − 2 = 1, backward cf(C, B) = 2. C→D: forward cf(C, D) = 1, backward cf(D, C) = 5. There is no augmenting path: the two edges leaving the source are saturated, and no edge leaves S in the residual network.

  2. In the second example network (Figure 8.10), what is the capacity of the cut S = {S, 1, 3}? Why is this cut not a minimum cut?

    Answer

    The edges going from S to T are 1 → 2 (4), 1 → 4 (8), and 3 → 4 (9): 4 + 8 + 9 = 21. The edges S → 1, S → 3, and 1 → 3 have both endpoints on the S side. Since the maximum flow is 19, a cut of capacity 21 cannot be minimum; the minimum cut is {S, 3} (19).

  3. Which paths does Edmonds-Karp find on the first example network (Figure 8.1)? How many augmentations and how many BFS runs does it make?

    Answer

    S → A → B → T (2), S → C → D → T (3), and S → A → B → C → D → T (2). The first two paths have 3 edges, the third 5. There are 3 augmentations; the fourth BFS cannot reach the sink. In total 4 BFS runs, maximum flow 7.

  4. Which paths does Ford-Fulkerson with a DFS that tries neighbors in index order (s, 1, 2, 3, 4, t) find on the network of Figure 8.17? How many augmentations does Edmonds-Karp make on the same network?

    Answer

    Six augmentations are made: s→1→2→4→3→t (7), s→1→2→4→t (3), s→1→3→2→4→t (1), s→1→3→t (5), s→2→1→3→t (6), s→2→3→t (1). The flow grows as 7, 10, 11, 16, 22, 23. The edge 2 → 1 on the fifth path is an original edge; 2 → 3 on the sixth path is the backward edge of 3 → 2. Edmonds-Karp reaches 23 on the same network with 3 augmentations.

  5. How many phases does Dinic's algorithm make on the first example network? What are the levels and the blocking flow in each phase?

    Answer

    Phase 1: the levels are S = 0; A, C = 1; B, D = 2; T = 3. B → C is not used because it goes back a level. The blocking flow is S → A → B → T (2) and S → C → D → T (3); |f| = 5. Phase 2: the levels are S = 0, A = 1, B = 2, C = 3, D = 4, T = 5; the path is S → A → B → C → D → T (2), |f| = 7. The third BFS cannot reach the sink. 2 phases, 3 BFS runs.

  6. In the first example network, if the capacity of the edge B → T is raised from 2 to 5, does the maximum flow change? In how many phases does Dinic finish?

    Answer

    It does not change; it stays 7. The capacity of the cut ({S}, the rest) is still 4 + 3 = 7, and this edge is not in that cut. Dinic finishes in a single phase: in the level graph S → A → B → T carries 4 and S → C → D → T carries 3 units. The second BFS cannot reach the sink.

  7. In the first example network, if at most 3 units of flow can pass through vertex B, how is the problem modeled and what is the maximum flow?

    Answer

    B is split into the vertices Bin and Bout; an edge of capacity 3 is placed between them. The edges become A → Bin (4), Bout → C (3), and Bout → T (2). The maximum flow is 6: for example 3 units through B (2 directly to the sink, 1 to C), and 3 units through S → C. The minimum cut consists of the edges S → C (3) and Bin → Bout (3): 6.

  8. What is the largest number of edge-disjoint paths from S to T in the second example network? How is this number reached with maximum flow?

    Answer

    Set all capacities to 1 and compute the maximum flow. The result is 2; for example S → 1 → 2 → T and S → 3 → 4 → T. Since only two edges leave the source (the cut {S} has capacity 2), a third edge-disjoint path is impossible.

  9. Push–relabel is started on the first example network. What are the initial heights and excesses? If A is chosen as the active vertex, what are the first two operations?

    Answer

    h(S) = 6, and h = 0 at all other vertices. S → A and S → C are saturated: e(A) = 4, e(C) = 3. The residual neighbors of A are B (h = 0) and S (a backward edge, h = 6); neither is one step below. First a relabel: h(A) = 1 + min(0, 6) = 1. Then a push: δ = min(e(A), cf(A, B)) = min(4, 4) = 4; e(A) = 0, e(B) = 4.

8.13Further reading

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 24: presents flow networks, the proof of the max-flow min-cut theorem, the Edmonds-Karp analysis, and bipartite matching with detailed proofs; the Edmonds-Karp trace network in these notes is from this book.
  • J. Kleinberg and É. Tardos, Algorithm Design (2006), Chapter 7: treats maximum flow as a modeling tool; presents applications such as image segmentation, project selection, and airline scheduling with worked examples.
  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 6.4: codes the shortest-path version of Ford-Fulkerson in Java with edge objects and shows the residual network in an object-oriented design.
  • A. V. Goldberg and R. E. Tarjan, “A New Approach to the Maximum-Flow Problem” (1988): gives the push–relabel algorithm, its invariants, and the O(V³) analysis of the FIFO version from the original source.

8.14References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 24: Maximum Flow).
  2. E. A. Dinic, “Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation”, Soviet Math. Doklady 11, 1970.
  3. J. Edmonds, R. M. Karp, “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems”, Journal of the ACM 19(2), 1972.
  4. L. R. Ford, D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics 8, 1956.
  5. A. V. Goldberg, R. E. Tarjan, “A New Approach to the Maximum-Flow Problem”, Journal of the ACM 35(4), 1988.
  6. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2006 (Chapter 7: Network Flow).
  7. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 6.4: Maximum Flow).

Related pages: Chapter 8 slides · © Sercan Külcü. All rights reserved.