Motivation
The residual-network method produces a maximum flow when no augmenting path remains. With integer capacities, arbitrary augmentations terminate after a number of steps bounded by a numerical capacity sum. That bound can be exponential in the number of bits used to encode the capacities. Choosing a shortest residual path gives a stronger guarantee independent of their magnitudes.
The algorithm is commonly called Edmonds–Karp. Its progress measure is not the flow value, which can increase by an arbitrarily small amount for real capacities, but the breadth-first distance of vertices in the residual network.
Definitions
Definition 3.9.1
(Capacitated network and residual arcs)
Let be a finite directed graph with distinct source and sink , and nonnegative capacities. A feasible flow and its value are as in the companion maximum-flow unit. Each original edge has a forward residual arc and a reverse residual arc when their residual capacities are positive. Keep arc identities even if opposite original edges create parallel residual arcs.
Definition 3.9.2
(Shortest augmenting path, distance and critical arc)
Start with the zero flow. At each iteration, run breadth-first search (BFS) in the current residual network and augment along a shortest – path by its positive bottleneck. Stop when no such path exists. Let be the BFS distance from to in the residual network of flow , with for unreachable vertices. An arc is critical for an augmentation if its residual capacity equals the path bottleneck and therefore becomes zero.
Theorems
Theorem 3.9.3
(Residual distances never decrease)
After an augmentation along a shortest residual – path, every residual distance from is at least its previous value, with ordered above finite values.
Theorem 3.9.4
(Polynomial augmentation bound)
The shortest-augmenting-path algorithm performs augmentations. With adjacency lists, after removing vertices unreachable from in the original graph, the total time is for nonempty edge sets under unit-cost exact arithmetic.
Proof sketch or proof idea
Proof
(Residual distances never decrease)
Suppose some distance decreases after an augmentation. Choose a vertex with decreased distance whose new distance is smallest, and let be the last arc of a new shortest path. Then , and 's distance did not decrease by the choice of . If was already residual before the augmentation, the old shortest-path inequality gives
a contradiction. Thus the arc is newly residual. It is the reverse of a path arc used by the augmentation. Along the old shortest path, . Since did not decrease, , again a contradiction. This also rules out a previously unreachable vertex becoming reachable.
Proof
(Each arc is critical only a linear number of times)
Fix a labeled residual arc . If it is critical, it is saturated and disappears. Before that same arc can be critical again, some later augmentation must use its paired reverse arc , making positive again. At the later use of the reverse arc, shortest-path distances satisfy . Distances never decrease, and at the earlier critical use . Therefore has increased by at least two between those events. A finite BFS distance is at most , so each labeled residual arc can become critical only times. Every augmentation has at least one critical arc, and there are at most labeled residual arcs, proving the augmentation bound.
Proof X-ray
A critical arc cannot return cheaply
The main move is to measure progress by BFS distance instead of flow value. Monotonicity rests on one observation: an augmentation along a shortest path creates only reverse arcs that point backward along that path, from distance to distance , and such an arc never offers a shortcut. The count of critical arcs adds a second ingredient. When a saturated arc is later restored, its reverse was used on a shortest path, so at that time, whereas at the saturation . Because cannot have decreased, has risen by at least two. A finite distance is at most , so an arc can be critical only times. Without the shortest-path rule neither relation is available, and the counterexample in the section on common mistakes shows that the number of augmentations can then depend on the capacities.
Proof
(Cost of the algorithm and its termination certificate)
Vertices unreachable from in the original graph cannot become reachable through residual updates: a newly created reverse arc joins two vertices already on an augmenting path. Remove such vertices once in time. The remaining relevant graph has at most vertices, so one BFS and augmentation cost . Combining this with augmentations gives the stated bound. If is removed, the zero flow is already maximum.
No augmenting path at termination gives a cut of capacity equal to the flow value by the companion max-flow/min-cut proof. Thus the returned flow is maximum. The argument applies to real capacities as a mathematical exact-arithmetic algorithm; binary bit complexity and numerical tolerances are separate questions.
Worked examples
Worked example 3.9.5
(A shortest augmenting path)
If residual paths and both exist, BFS selects the two-edge path before the three-edge path. It may choose either path only when their edge counts tie; capacities do not determine BFS distance.
Worked example 3.9.6
(A critical bottleneck)
If a residual path has arc capacities , its bottleneck is two. Augmenting by two saturates the middle arc, making it critical. Other arcs may also be critical if they have the same minimum residual capacity.
Worked example 3.9.7
(A reverse arc can appear)
Sending one unit along an original edge creates one unit of reverse residual capacity if none existed for that edge. Using the reverse arc later cancels part of the original flow; it is not a new original edge.
Common mistakes
Common mistake
(Shortest means fewest arcs, not the largest bottleneck)
BFS ignores residual-capacity magnitudes when measuring path length. A path of two arcs with bottleneck one is shorter than a three-arc path with bottleneck one hundred. Choosing the latter for its larger bottleneck is not the algorithm analyzed here.
Counterexample mode
Arbitrary augmenting paths can need many steps
The shortest-path rule cannot be dropped from the augmentation bound. Let be a positive integer. Take edges , , and of capacity , and an edge of capacity . Suppose the algorithm alternately augments along and, using the reverse of , along . Every such path has bottleneck exactly one: the first because of , the second because after the first augmentation the reverse arc has residual capacity one. Each augmentation adds one unit, the edge alternates between carrying one unit and none, and each of the four outer edges is used times. After augmentations the flow value is , which is maximum because the edges leaving have total capacity . The number of steps grows with , which is exponential in the number of bits of . Breadth-first search instead chooses and , each with bottleneck , and finishes in two augmentations. The repaired claim keeps the shortest-path rule, which gives a bound that does not depend on .
Common mistake
(Flow value is not the progress measure)
A strict increase in flow value does not by itself bound the number of augmentations for arbitrary real capacities. The polynomial proof instead tracks critical arcs and BFS distances. Parallel residual arcs must be distinguished by their original-edge identities when applying the reverse-arc argument.
Why distances cannot decrease
The distance proof compares two residual graphs, before and after one shortest-path augmentation. An arc that remains positive was already present; an arc can appear only when its paired reverse arc was used by the augmentation. Capacities can increase or decrease without changing graph membership, but BFS distance depends only on whether an arc is present, not on its numerical capacity.
If a newly shorter path existed, choose a decreased vertex of smallest new distance. Its predecessor on a new shortest path has smaller new distance and therefore is not a decreased vertex. If the predecessor arc existed before, the old shortest path to followed by that arc would contradict the assumed decrease at . If it is new, the augmentation used the opposite arc from to . Because the augmenting path was shortest, the old distance rises by exactly one along that path edge. The two inequalities then force the new distance to to be at least two larger than its old distance, the opposite of a decrease.
A shortest augmenting path has no repeated vertex: removing a repeated-vertex segment would give a shorter path. Every prefix of a shortest path is also a shortest path to its endpoint, which justifies the distance relation along its arcs. A BFS implementation may choose any shortest path when several exist; the proof does not require a particular tie-breaking order.
Worked example 3.9.8
(Residual distance rather than capacity)
Suppose BFS assigns distances , and , and the chosen path is . After sending flow, a reverse residual arc may appear. That new arc points from distance one back to distance zero; it does not by itself create a shorter route from to . The general proof handles all new reverse arcs together, not only this one.
Counting critical arcs carefully
When the residual capacity of a labeled arc becomes zero, it can regain capacity only if an augmentation uses the paired reverse residual arc. If the original graph contains an edge in each direction, these are still two distinct original edges, each with its own residual pair. An arc from to that belongs to the other original edge is not automatically the paired reverse of the saturated arc. Keeping these identities avoids attributing a capacity increase to the wrong edge.
Suppose is critical at some iteration. Along that iteration's shortest path, the old distances satisfy . When its paired reverse is later used, the current shortest-path distances satisfy . Distance monotonicity says the later distance of is at least its earlier distance. Consequently the later distance of is at least the earlier distance of plus two. If becomes critical again after that, monotonicity preserves this increase.
A vertex on an augmenting path is reachable and has distance at most . Thus the tail distance of one labeled arc can increase by two only times before that arc can no longer be critical. Choose one critical arc for each augmentation; this charges every augmentation to an arc, while each arc receives only charges. There may be several tied bottlenecks on a path, but choosing any one for the charge is sufficient.
From path search to total cost
In an adjacency-list residual representation, each original edge contributes at most two labeled residual arcs. BFS examines each currently available arc at most once, and predecessor pointers recover a shortest path. The augmentation updates each arc on that path and its paired reverse capacity. An implementation must store those pair links consistently so that canceling flow changes the correct original edge.
If a vertex is unreachable from in the original directed graph, it has no incoming original edge from the originally reachable set. Initially it is unreachable in the residual graph. Every augmentation uses only currently reachable vertices, so any reverse arc it creates also joins currently reachable vertices. By induction no excluded vertex becomes reachable. Removing them cannot eliminate an augmenting path. If the remaining set contains vertices, each except is reached by at least one original edge, so .
After this preprocessing, each BFS and path update takes time. Multiplying by the augmentation count and adding preprocessing gives for a nonempty edge set. The looser follows immediately without the preprocessing refinement. These bounds count exact arithmetic and graph operations, not the bit complexity of arbitrary real numbers.
Flow value, termination and certificates
Each augmentation preserves capacity constraints and conservation because it adds the bottleneck along residual directions and subtracts it along reversed original edges. Its value strictly increases, but the polynomial termination proof does not depend on a minimum positive increase. This is why the structural argument works for real capacities in the mathematical model, while an integer-capacity proof based on unit increases has a numeric capacity bound.
When BFS cannot reach , the residual vertices reachable from form one side of a cut. Every original edge leaving that side is saturated; every original edge entering it carries zero flow, or its reverse would be a residual arc leaving the side. The cut capacity equals the flow value. This pair is a checkable optimality certificate, independently of how many augmentations were used.
The shortest-path choice is needed for the distance monotonicity proof. Arbitrary augmenting paths may be useful and correct when they terminate, but the critical-arc count above cannot be applied to them without showing the same distance relations. Nor does the bound say that the path with the largest bottleneck is shortest; BFS uses the number of residual arcs.
Summary
Shortest residual paths give nondecreasing BFS distances. Between repeated saturations of the same labeled arc, a reverse use forces its tail distance to rise. Summing the resulting critical-arc bound proves a polynomial number of augmentations and, together with the cut certificate, a maximum flow.
Exercises
Quick check
(Which path is shorter for BFS: two residual arcs or three, regardless of capacities?)
BFS counts arcs, not capacity.
Solution · Answer
The two-arc path is shorter.
Quick check
(What happens to a critical arc's residual capacity after augmentation?)
Compare its capacity with the bottleneck.
Solution · Answer
Its residual capacity becomes zero, so it disappears from the residual network until capacity is restored by a use of its reverse arc.
Quick check
(Why must every augmentation have at least one critical arc?)
Look at the arc that attains the minimum.
Solution · Answer
A finite nonempty path has at least one arc attaining its positive minimum residual capacity, and that arc is saturated.
Quick check
(What proves maximum flow once no augmenting path remains?)
Consider the vertices reachable from .
Solution · Answer
The set reachable from the source defines a cut whose capacity equals the feasible flow value. Weak duality then shows that the flow is maximum and the cut is minimum.
Exercise 3.9.9
(Run Edmonds–Karp on the network with capacities , , , and . Give the BFS distance of at each augmentation and certify the maximum flow value.)
Core
All other pairs of vertices have no edge.
Solution(3)
- 1
Augment along the two-arc paths
The distance of is . The bottlenecks are and , so after these two augmentations the flow value is . The residual capacities are now on , on , on and on .
Because: Both and have two arcs, so either may be taken first.
- 2
Search again
Key step
The distance of rises to , as the theorem allows. The path has bottleneck , so the flow value becomes .
Because: The only residual route from goes through and the arc .
- 3
Certify optimality
Now and are both saturated, so BFS reaches only . The cut has capacity , equal to the flow value, so the maximum flow value is . The distances of were , which never decrease.