Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 36 ยท Planarity and Flows

Maximum Flow and the Ford-Fulkerson Method

Understand flow networks, residual graphs and augmenting paths, then implement Ford-Fulkerson and Edmonds-Karp in Python and verify them against SciPy's maximum_flow.

Water pipes, road traffic, data packets and electrical current all share one question: given the capacity of each connection, how much can you push from a source to a destination? Graph theory answers with the maximum flow problem. It is one of the most useful tools in the field, because dozens of other problems, from bipartite matching to image segmentation and airline scheduling, reduce to it.

Flow networks

A flow network is a directed graph with a capacity c(u, v) โ‰ฅ 0 on each edge, a source s and a sink t. A flow f assigns each edge a value f(u, v) such that:

  1. Capacity constraint: 0 โ‰ค f(u, v) โ‰ค c(u, v).
  2. Conservation: for every vertex other than s and t, flow in equals flow out.

The value of a flow is the net amount leaving the source. The goal is a flow of maximum value.

A greedy attempt, pushing flow along any path until stuck, may block itself: an early choice can use up an edge that a better arrangement needs. The key idea that fixes this is the residual graph.

The residual graph

Given a flow f, the residual graph has an edge u โ†’ v with residual capacity c(u, v) โˆ’ f(u, v) (room left to push more), and an edge v โ†’ u with capacity f(u, v) (the amount we may cancel by sending flow back). Pushing flow along a reverse edge undoes earlier flow, which is what lets the algorithm recover from bad early choices.

An augmenting path is a path from s to t in the residual graph. Its bottleneck is the smallest residual capacity on it. Pushing the bottleneck amount along the path increases the flow value by that amount.

Ford-Fulkerson in four steps

Residual graph Forward room and backward undo
Find an s-t path Any path with positive room
Bottleneck Smallest residual on the path
Push and update Add forward, subtract backward

Stop when no augmenting path exists

1 / 2

Ford-Fulkerson and Edmonds-Karp in code

The Ford-Fulkerson method repeats the augment step until no augmenting path exists. It leaves open how to pick the path. Edmonds-Karp is the specialization that always takes a shortest path by BFS, which gives a clean bound: at most O(VยทE) augmentations, so O(VยทEยฒ) total time, independent of the capacities. A DFS choice works too, but with integer capacities its running time can be proportional to the flow value itself.

Python Edmonds-Karp max flow with traced augmentations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every printed augmentation uses a shortest path in the residual graph. In the final residual graph the vertices reachable from s form one side of a minimum cut, which is the subject of the next lesson.

Why the algorithm can be slow with bad path choices

With a poor path choice, Ford-Fulkerson can zigzag. Consider two routes, s โ†’ a โ†’ t and s โ†’ b โ†’ t, both with capacity C, plus a tiny cross edge a โ†’ b of capacity 1. If the algorithm alternates between the paths s โ†’ a โ†’ b โ†’ t and s โ†’ b โ†’ a โ†’ t (using the cross edge forwards, then backwards), each augmentation adds just 1 unit, so 2C augmentations are needed to reach the flow of 2C. Choosing the two direct paths finishes in two steps.

Python Zigzag versus shortest paths on the classic bad network

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Make C = 1000000 and the zigzag takes two million rounds while Edmonds-Karp still needs two. That is the practical reason to prefer BFS (or Dinic's algorithm) for path selection.

Checking against SciPy

SciPy ships a fast, tested implementation: scipy.sparse.csgraph.maximum_flow takes a sparse matrix of integer capacities. Comparing your own code with a library is a great way to catch bugs.

Python Compare with scipy.sparse.csgraph.maximum_flow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The flow value matches the 19 found by Edmonds-Karp. The individual edge flows may differ because maximum flows are generally not unique.

Useful facts

  • Integrality theorem: if all capacities are integers, there is a maximum flow with integer values on every edge. Ford-Fulkerson with integer capacities finds one.
  • Vertex capacities are modeled by splitting a vertex v into v_in โ†’ v_out with the capacity on the new edge.
  • Multiple sources or sinks need a super-source and super-sink.
  • Undirected edges become two opposite directed edges of the same capacity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an edge v โ†’ u in the residual graph with capacity f(u, v) represent?

    Sending flow along the reverse residual edge reduces the current flow on u โ†’ v, which lets later augmentations undo earlier choices.
  2. 2. What distinguishes Edmonds-Karp from the generic Ford-Fulkerson method?

    Choosing the shortest augmenting path bounds the number of augmentations by O(V ร— E), so the total time is O(V ร— Eยฒ) regardless of capacity values.
  3. 3. A flow network has integer capacities. What does the integrality theorem guarantee?

    Every augmentation changes flows by integer bottlenecks, so Ford-Fulkerson ends with an integer flow.
  4. 4. In the network of the zigzag example (two routes of capacity C and a cross edge of capacity 1), how many augmentations can the worst path choice need?

    Alternating through the cross edge forward and backward adds only one unit of flow per augmentation, so reaching 2C takes 2C augmentations.

Summary

  • A flow respects capacities and conservation; the maximum flow is the largest net flow from source to sink.
  • The residual graph has forward remaining capacity and backward edges that allow undoing flow.
  • Ford-Fulkerson augments along any residual s-t path; Edmonds-Karp picks shortest paths and runs in O(VยทEยฒ).
  • With integer capacities the maximum flow can be chosen integral.
  • Always validate a hand-written flow against a library such as SciPy.

Next: Minimum Cuts and Flow Applications