Does shortest path mean least monetary cost?

No. Edmonds-Karp uses the fewest residual edges for each augmentation.

Why are reverse edges needed?

They allow some previously assigned flow to be canceled and redirected as better overall routing becomes available.

Does the algorithm return only one route?

No. A maximum flow can be distributed across several routes, and NetworkX's routine returns a residual network representing the result.

AI Glossary / Graphs and symbolic AI / Intermediate

Edmonds-Karp

Definition

Edmonds-Karp is an algorithm for finding a maximum flow from a source to a sink in a capacitated network. It repeatedly finds an augmenting path with the fewest edges in the residual network using breadth-first search, then sends as much additional flow along that path as its remaining capacities permit.

What it means

A flow network models how a quantity can move through connections with limited capacities. Intermediate nodes normally conserve flow: what enters must leave. The objective is to maximize the total amount reaching the sink from the source.
Edmonds-Karp is a specific augmenting-path method. Its use of shortest residual paths refers to the number of edges, not to distance, price, or capacity. It does not directly solve every logistics problem: multiple commodities, transit times, losses, or costs require additional modeling or different algorithms.

How it works

Begin with zero flow and construct residual capacities, which describe how existing flow can be increased or redirected. Breadth-first search finds a source-to-sink path using edges with positive residual capacity. The path's bottleneck is the smallest such capacity. Add that amount to the flow and update both forward and reverse residual possibilities.
Repeat until no augmenting path remains, at which point the flow is maximum under the standard assumptions. Reverse residual edges allow earlier routing choices to be undone; they do not necessarily represent physical reverse links. The standard complexity bound is O(V x E squared), where V and E count vertices and edges.

Three practical examples

A network-capacity exercise calculates the maximum single-commodity throughput allowed by a modeled set of links.
A bipartite matching problem is transformed into a unit-capacity flow network and solved using a maximum-flow algorithm.
A planning analyst identifies a bottleneck cut in a simplified supply network before investigating practical capacity changes.

Think of it this way

Think of adjusting water through pipes while respecting each pipe's capacity and conserving flow at junctions. The analogy captures throughput and bottlenecks. It is limited because residual reverse edges represent mathematical cancellation of prior assignments, and the basic model omits pressure, travel time, leakage, and other physical effects.

Worked example

Use a directed network with capacities S-A = 3, S-B = 2, A-T = 2, B-T = 3, and A-B = 1. Start with zero flow. A breadth-first augmenting path S-A-T has bottleneck min(3,2) = 2, so send two units along it.
Another shortest available path is S-B-T, with bottleneck min(2,3) = 2. The total flow becomes four. One unit of capacity remains on S-A and B-T, while A-B has capacity one. The path S-A-B-T can therefore carry one more unit, bringing the total to five.
The final flows conserve quantities: A receives three and sends two to T plus one to B; B receives two from S plus one from A and sends three to T. The source has only 3 + 2 = 5 outgoing capacity, so no flow can exceed five. Since the constructed flow reaches that bound, it is maximum. Tie-breaking could choose the two initial shortest paths in the opposite order without changing this conclusion.

Illustrative case study

At fictional Elm Throughput, a team adds a high-capacity connection inside a network and expects the maximum delivery rate to rise. A flow analysis shows that the source-side cut remains unchanged, so the modeled maximum does not improve. The team investigates the limiting connections instead.
This fictional case illustrates bottleneck reasoning. It does not claim that actual deliveries match the static flow model, especially if operating hours, multiple goods, or transfer delays have been omitted.

Common misconceptions and mistakes

Do not choose a path merely because it has the largest capacity and call the result Edmonds-Karp. Its defining path-selection rule is breadth-first search in the residual network.
Do not ignore reverse residual edges. They permit rerouting and are essential to avoiding premature conclusions from earlier choices. Capacity is an upper bound, not an automatically realized flow. Also, maximum flow is different from minimum-cost flow: two equally large flows can have different costs. In NetworkX, omitted capacity attributes can be interpreted as infinite, so missing data can materially change the problem rather than simply defaulting to zero.

Business use

Businesses should specify the commodity, time basis, source, sink, and meaning of every capacity. Check conservation assumptions and whether the system permits the modeled splitting of flow. Use a minimum cut to explain an upper bound on throughput, while recognizing that several cuts may be equally limiting. When applying the NetworkX routine, inspect its returned residual network and flow value rather than assuming it returns a simple path. Confirm that no early cutoff has been mistaken for a proof of maximality.

Check your understanding

In the worked example, could the total flow be six without changing an edge capacity?

Answer: No. The cut separating S from all other nodes has capacity five. That upper bound applies to every feasible flow, and the example already achieves it.

Related terms

Maximum Flow
Breadth First Search
augmenting path
residual network
bottleneck capacity
minimum cut
flow conservation
Ford-Fulkerson method

Learn next

Reduce B-T's capacity from three to one in the worked network. Recompute feasible flow and identify a cut that proves the new maximum. Then explain why increasing A-B alone cannot overcome an unchanged sink-side capacity limit.

Sources

NetworkX, edmonds_karp, official reference and residual-network conventions: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.edmonds_karp.html NetworkX, official algorithm implementation showing breadth-first augmentation: https://networkx.org/documentation/stable/_modules/networkx/algorithms/flow/edmondskarp.html

Previous: Edit distance Next: EDU