Finding the Edmonds-Karp path through flow networks

When you stare at a map of Sydney's morning commute, the tangled streams of cars pouring toward the Harbour Bridge and through the Eastern Distributor look almost like a graph in their own right: nodes for intersections, edges for roads, each lane with a hard ceiling of how many vehicles it can push through before gridlock sets in. That mental picture is the same shape as a flow network in computer science, and finding the busiest arrangement a network can sustain is exactly what the Edmonds-Karp algorithm does. It is the BFS-driven cousin of the Ford-Fulkerson method, and it is one of those quietly essential pieces of theory that powers everything from airline scheduling to image segmentation. This tutorial walks through how it works, why BFS is the secret ingredient, and where it sits among other approaches to the max flow problem.

Flow problems show up in places you would not expect: assigning shifts to nurses across a Brisbane hospital, balancing packets through a content delivery network, deciding how much freight a Melbourne logistics firm can route through its depots before a choke point bites. The Edmonds-Karp variant gives you a dependable, polynomial-time way to push as much flow as possible from a source to a sink, which is why it remains a fixture in algorithms courses and in the toolkit of working engineers around the country and beyond.

What a flow network actually looks like

A flow network is a directed graph with three extra rules bolted on. Each edge carries a capacity, which is a non-negative number standing in for the maximum amount of stuff that can travel along that edge per unit of time. There is one vertex marked as the source and another marked as the sink, and every other vertex simply moves whatever arrives at it onwards. Flow itself is conserved: what goes in must come out, except at the source, where it is created, and the sink, where it vanishes.

The max flow problem asks for the largest total value you can push from source to sink without exceeding any capacity. It is one of the cleanest, oldest problems in combinatorial optimisation, and it sits beside shortest paths and minimum spanning trees as a foundational graph primitive. The famous max-flow min-cut theorem ties it together: the maximum flow value equals the minimum total capacity of any cut that separates the source from the sink. That duality is not just an elegant curiosity; it gives you a certificate. If a flow has reached a value that no cut can beat, you know it is optimal.

In practice, networks often have thousands of vertices and tens of thousands of edges, which is why the algorithm you pick matters. An algorithm that runs in milliseconds on a classroom example may crawl for hours on a production-sized instance, so the choice between Ford-Fulkerson with arbitrary augmenting paths and Edmonds-Karp with BFS is rarely a stylistic one.

Why Edmonds-Karp improves on Ford-Fulkerson

The classic Ford-Fulkerson method keeps finding an augmenting path through whatever means you like, then pushes flow along it until no path exists. It works, but its running time is bounded by the value of the maximum flow multiplied by the cost of finding a path, which can be exponential if you are unlucky with the paths you choose. The classic counterexample is a graph where a careless choice of augmenting paths makes the algorithm rebuild the same bottlenecks over and over with a single unit of flow at a time. She'll be right, you might think, but the worst case is genuinely nasty.

Edmonds-Karp fixes that weakness by being prescriptive: it always picks the shortest augmenting path, measured in number of edges, and it finds that path with breadth-first search. That one decision changes everything. With BFS, the algorithm is guaranteed to terminate in at most O(VE²) operations, where V is the number of vertices and E the number of edges. The proof hinges on a slick observation about how the level structure of the BFS tree evolves: each augmentation either raises the distance from the source to some vertex, or saturates a shortest path. Since distances are bounded above by V and edges get saturated at most O(V) times, the whole thing is comfortably polynomial.

If you are coming from a background where you learned greedy local search for optimisation, it is worth seeing how different this mindset is. A walk through A Tutorial on the Hill Climbing Algorithm for Optimization shows a method that gets stuck in local maxima; Edmonds-Karp, by contrast, has a clean global guarantee baked into it. That contrast is one of the most useful lessons in an algorithms course, and it shows up the moment you start comparing approaches on real benchmarks.

Walking through the algorithm step by step

The algorithm is short enough to memorise, which is part of its appeal. Start by constructing a residual graph: for every edge (u, v) with capacity c and current flow f, you create a forward edge (u, v) with remaining capacity c - f, and a backward edge (v, u) with remaining capacity f. The residual graph lets flow be undone, which is what makes iterative augmentation correct.

Then you run BFS from the source in the residual graph until you either reach the sink or exhaust the frontier. If BFS reaches the sink, you have a shortest augmenting path; walk back along the parents, find the bottleneck capacity (the smallest remaining capacity on that path), and push that much flow along each edge, flipping the residual capacities as you go. If BFS cannot reach the sink, you are done: there is no augmenting path left, so by the max-flow min-cut theorem the current flow is optimal.

Pseudocode for the inner loop looks roughly like this:

bfs(s, t):
    for each vertex v: parent[v] = -1, visited[v] = false
    queue = [s]
    visited[s] = true
    while queue not empty:
        u = queue.pop_front()
        for each edge (u, v) in residual:
            if not visited[v] and residual[u][v] > 0:
                parent[v] = u
                visited[v] = true
                if v == t: return true
                queue.append(v)
    return false

Each successful BFS is followed by an augmentation; each unsuccessful BFS ends the algorithm. Because BFS over a graph with V vertices and E edges costs O(V + E), and there are at most O(VE) augmentations in total, the overall bound O(VE²) drops out cleanly.

A concrete example

Imagine a small parcel routing problem: a depot in Parramatta (S) sends parcels to a distribution hub in the Sydney CBD (T), with intermediate sorting facilities at Strathfield, Chatswood, and North Sydney. Capacities represent how many pallets of parcels each road link can handle per hour, no dramas.

Edges and capacities, in pallets per hour:

• S → Strathfield: 8
• S → Chatswood: 6
• Strathfield → Chatswood: 4
• Strathfield → North Sydney: 6
• Chatswood → North Sydney: 4
• Chatswood → T: 5
• North Sydney → T: 9

Round one: BFS from S finds S → Strathfield → North Sydney → T with bottleneck 6. Push 6. Round two: BFS finds S → Chatswood → T with bottleneck 5. Push 5. Round three: BFS finds S → Strathfield → Chatswood → T with bottleneck 4. Push 4. Round four: BFS finds S → Chatswood → North Sydney → T with bottleneck 1, using the residual on Chatswood → North Sydney. Push 1. Round five: BFS cannot reach T. Done.

Total flow: 6 + 5 + 4 + 1 = 16 pallets per hour, which is optimal because the cut separating {S, Strathfield} from the rest has capacity 6 + 6 + 4 = 16, matching the flow. That is the min cut, and it doubles as a sanity check on the algorithm. Notice how BFS kept picking the shortest path and how the residual graph let us undo the S → Chatswood → T choice later by routing through Chatswood → North Sydney → T using the reverse edge left behind. Without those residual edges, fewer parcels would have made it through, which would be a poor outcome during peak season.

Where the algorithm lives in real code

In production code, you rarely implement Edmonds-Karp from scratch. NetworkX in Python ships with a max flow routine that uses Edmonds-Karp by default, and it is the right hammer for graphs up to a few thousand nodes. For truly large graphs, the Dinic algorithm takes over with its blocking-flow step, dropping the practical running time by a large constant. Push-relabel methods become attractive once the graph has hundreds of thousands of edges, since they work locally rather than scanning the entire network each iteration.

Australian engineering teams lean on these tools regularly. The data teams at the big four banks run flow problems to optimise cash dispersal through ATM networks stretching from Perth to Cairns; Atlassian and Canva have teams that model capacity planning with network flow; logistics firms around the Port of Melbourne use max flow to schedule containers through constrained yard space. None of them hand-roll Edmonds-Karp in a hot path, but every one of their engineers is expected to recognise the pattern when it shows up in a design review, mate.

If you would like to read more about the optimisation mindset that surrounds these algorithms, the contact page lists several follow-ups worth chasing, including interview prep notes and pointers to larger worked examples.

A few implementation tips worth keeping in your back pocket. Use adjacency lists rather than adjacency matrices once the graph has more than a couple of hundred vertices, because every iteration walks the edges anyway. Treat the residual graph implicitly: store the original capacity and current flow, and compute the remaining capacity on the fly rather than maintaining two copies of the edge set. Always initialise the BFS queue carefully, since off-by-one mistakes in the parent array are a classic source of silent bugs that only show up on asymmetric graphs.

Edmonds-Karp is not just an algorithm; it is a worked example of how a small structural choice, shortest augmenting paths found by BFS, can turn an exponential worst case into a polynomial one. That same pattern shows up again and again: a greedy local rule applied globally beats a cleverer-looking global rule applied locally. Once you have seen it in the flow setting, you start spotting it everywhere.