Why Search the Residual Network by Breadth First?
An augmenting-path method can choose many different routes from the source to the sink. The route matters: a path with large residual capacities may seem attractive, but repeatedly making such choices can lead to an inefficient sequence of augmentations. The Edmonds-Karp rule makes the choice precise: in each residual network, use breadth-first search (BFS) to find an augmenting path with the fewest arcs. BFS measures path length by the number of arcs, not by their capacities.
Throughout, a network is a finite directed graph with a source \(s\), a distinct sink \(t\), and a nonnegative capacity \(c(e)\) on each directed arc \(e\). A flow \(f\) satisfies \(0\le f(e)\le c(e)\) on every arc and conservation at every vertex other than \(s\) and \(t\). Its value is the net flow out of \(s\). A residual arc records a possible change to the current flow: an original arc \(u\to v\) has forward residual capacity \(c(u\to v)-f(u\to v)\), and its reverse residual arc \(v\to u\) has residual capacity \(f(u\to v)\). Only residual arcs with strictly positive capacity can be used. When arcs need to be distinguished, regard each residual arc as labelled by the original arc and whether it is forward or reverse.
BFS explores vertices in order of their distance in number of arcs from \(s\). It maintains a queue and, when it first discovers a vertex, records its predecessor. Following predecessor pointers backwards from \(t\) recovers a shortest path. If two or more shortest paths exist, the order in which outgoing residual arcs are scanned can determine which one is found; any of the shortest paths is acceptable.
Why BFS Finds a Shortest Augmenting Path
Proof. Let \(L_k\) denote the vertices at distance \(k\) from \(s\), where distance is the fewest number of directed arcs in a path; \(L_0=\{s\}\). BFS processes vertices in nondecreasing order of distance. To justify this, vertices enter the queue when first discovered. A vertex at distance \(k\) is discovered while processing a vertex at distance \(k-1\), and is placed after vertices already waiting in the queue. Thus all discovered vertices at a smaller distance are processed before vertices at a larger distance. Inductively, when a vertex at distance \(k\) is processed, all vertices at distances less than \(k\) have already been processed, and each vertex reachable in at most \(k\) arcs has been discovered. Each discovered vertex is assigned a predecessor along an arc from a vertex one level nearer \(s\). Therefore, following predecessors from any discovered vertex gives a path whose length is its assigned distance. In particular, if \(t\) is discovered, this path has the minimum possible number of arcs. If \(t\) is never discovered, every vertex reachable from \(s\) has been explored, so no \(s\)-to-\(t\) path exists. The residual-network claim follows by treating positive-capacity residual arcs as the available directed arcs. \(\square\)
BFS may stop as soon as it discovers \(t\): the lemma shows that the predecessor chain then already has minimum length. Alternatively, it may finish processing the queue. Neither choice changes the shortest-path guarantee. A residual capacity affects whether an arc is available, but its numerical size does not affect BFS's distance labels.
The Edmonds-Karp Rule
For an augmenting path \(P\), let \(\delta\) be its bottleneck. On each forward residual arc, increase the corresponding original flow by \(\delta\); on each reverse residual arc, decrease the corresponding original flow by \(\delta\). This is why reverse arcs must be included in the search: they allow the algorithm to cancel part of an earlier choice and reroute that flow.
Proof. Let \(P\) be the path and let \(\delta\) be the least residual capacity on it. For a forward arc corresponding to an original arc \(e\), the update is \(f(e)\mapsto f(e)+\delta\). Since \(\delta\le c(e)-f(e)\), the updated flow is at most \(c(e)\), and it is still nonnegative. For a reverse residual arc corresponding to \(e\), the update is \(f(e)\mapsto f(e)-\delta\). Since \(\delta\le f(e)\), this updated flow is nonnegative and remains at most \(c(e)\). At an internal vertex of \(P\), the path brings in \(\delta\) units and sends out \(\delta\) units, counting a reverse arc as a decrease on its original arc. These changes preserve flow conservation there. The source sends an additional \(\delta\) units of net flow, and the sink receives an additional \(\delta\). Thus the updated flow is feasible and its value has increased by \(\delta\). \(\square\)
If the algorithm halts because there is no augmenting path, the augmenting-path characterization of maximum flows says that the current flow is maximum. That characterization was established earlier in the course. The shortest-path rule defines which augmenting path to select at each step; the characterization explains why the absence of any such path certifies optimality.
Tracing BFS and Its Path Choice
Worked Example: A Short Path Despite a Longer Route
Let the network have vertices \(V=\{s,a,b,c,t\}\) and directed arcs with capacities \(s\to a:5\), \(s\to b:5\), \(a\to t:1\), \(a\to c:4\), \(c\to t:4\), and \(b\to t:3\). Start with zero flow. Scan outgoing arcs in the displayed order.
BFS begins with queue \([s]\) and distance \(0\) at \(s\). Its trace is:
| Action | New discoveries | Queue afterward |
|---|---|---|
| Start | \(s\) has distance \(0\) | \([s]\) |
| Process \(s\) | \(a,b\) at distance \(1\) | \([a,b]\) |
| Process \(a\) | \(t,c\) at distance \(2\) | \([b,t,c]\) |
The predecessor pointers give \(s\to a\to t\), a path of \(2\) arcs. The other route \(s\to a\to c\to t\) has \(3\) arcs, and \(s\to b\to t\) is another shortest route of \(2\) arcs. With the specified scan order, BFS discovers \(t\) from \(a\) and selects \(s\to a\to t\). Its bottleneck is \(\min(5,1)=1\), so the update sends \(1\) unit on \(s\to a\) and \(a\to t\).
Check: the updated flows on \(s\to a\) and \(a\to t\) are both \(1\), and every other flow is \(0\). At \(a\), inflow and outflow are each \(1\); the flow value is \(1\). The path has \(2\) arcs, while the alternative through \(c\) has \(3\), as the BFS distances indicate.
Worked Example: Ties and Capacity Do Not Change the Search Rule
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a:2\), \(a\to t:2\), \(s\to b:5\), and \(b\to t:5\), and zero initial flow. Scan \(s\to a\) before \(s\to b\). After processing \(s\), BFS has queue \([a,b]\), with both vertices at distance \(1\). It processes \(a\) first, discovers \(t\) at distance \(2\), and records \(a\) as the predecessor of \(t\). Thus it selects \(s\to a\to t\).
The selected path has bottleneck \(\min(2,2)=2\). The other path, \(s\to b\to t\), also has \(2\) arcs, but its bottleneck is \(\min(5,5)=5\). BFS still selects the first path under the stated scan order: it minimizes the number of arcs, not maximizes the bottleneck. After augmentation, \(f(s\to a)=2\) and \(f(a\to t)=2\), so the flow value is \(2\). At \(a\), the incoming and outgoing flows are both \(2\); \(b\) still has zero inflow and outflow.
Check: both candidate paths have length \(2\), so neither is shorter. The chosen route's bottleneck is \(2\), computed from its two capacities; the unchosen route's bottleneck is \(5\), also computed from its two capacities. The BFS choice follows the distance rule, not a comparison of these bottlenecks.
Worked Example: A Shortest Path Uses a Reverse Residual Arc
Let \(V=\{s,a,b,t\}\), with directed arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), and \(b\to t\), each of capacity \(1\). Consider the feasible flow \(f(s\to a)=1\), \(f(a\to b)=1\), \(f(b\to t)=1\), and \(f(s\to b)=f(a\to t)=0\). Its value is \(1\): at \(a\), inflow and outflow are both \(1\), and at \(b\), inflow and outflow are both \(1\).
The positive residual arcs include \(s\to b\), \(b\to a\) (the reverse of \(a\to b\)), and \(a\to t\), each with residual capacity \(1\). BFS starts with \([s]\). Processing \(s\) discovers \(b\) at distance \(1\). Processing \(b\) discovers \(a\) at distance \(2\) using \(b\to a\). Processing \(a\) discovers \(t\) at distance \(3\) using \(a\to t\). The resulting path is \(s\to b\to a\to t\), and its bottleneck is \(\min(1,1,1)=1\).
Augment by \(1\): increase \(f(s\to b)\) from \(0\) to \(1\), decrease \(f(a\to b)\) from \(1\) to \(0\), and increase \(f(a\to t)\) from \(0\) to \(1\). The final flow has value \(2\). At \(a\), inflow \(1\) on \(s\to a\) equals outflow \(1\) on \(a\to t\); at \(b\), inflow \(1\) on \(s\to b\) equals outflow \(1\) on \(b\to t\). All five arc flows are between \(0\) and their capacity \(1\).
Check: the reverse residual step has cancelled the earlier unit on \(a\to b\); it has not sent flow on a new original arc \(b\to a\). The updated original-arc flows are \(1,1,0,1,1\) on \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), \(b\to t\), respectively. Their net flow out of \(s\) is \(1+1=2\), matching the computed value.
What the Rule Does—and Does Not—Measure
Each BFS level records a number of arcs: a vertex first found at level \(k\) is reached by a shortest residual path of \(k\) arcs. Capacities enter in two separate ways. First, an arc is eligible only if its residual capacity is strictly positive. Second, after the path is selected, the smallest residual capacity on it determines the augmentation amount. Keeping these roles separate avoids confusing shortest-path selection with a largest-capacity-path rule.
A common mistake is to choose the route with the largest bottleneck. In the second example, that would choose \(s\to b\to t\), since its bottleneck is \(\min(5,5)=5\). That calculation is correct for the bottleneck, but it is not the Edmonds-Karp selection rule: BFS chooses according to path length, and the stated scan order selects \(s\to a\to t\). The reverse mistake is to ignore reverse residual arcs. Doing so in the third example would miss the route that cancels \(a\to b\) and reroutes the flow, even though that route is available in the residual network.
Edmonds-Karp is therefore not a new update formula. It is the augmenting-path method with a specific path-selection rule: run BFS on positive residual arcs, recover a shortest path, and augment by its bottleneck. The algorithm's termination and running-time analysis require additional arguments about how residual distances and critical arcs behave; those claims do not follow merely from BFS finding a shortest path.
Check Your Understanding
Use the BFS distance rule and the residual capacities explicitly in each response.
- In a residual network, what does the distance label of a discovered vertex count?
- If two augmenting paths have the same minimum number of arcs but different bottlenecks, which one does BFS select, and what determines the choice between them?
- For an original arc carrying \(3\) units of flow, what is the capacity of its reverse residual arc?
- Why can a BFS path include a reverse residual arc, and what flow update does that represent?
- What does the absence of an augmenting path certify about a feasible flow?