The Distance Invariant
Edmonds–Karp chooses a shortest source-to-sink path in the current residual network, measured by number of arcs, and augments flow along that path. The key fact is that this operation cannot make any vertex closer to the source in the residual network. This remains true even though augmentation can create reverse arcs, which permit later augmentations to undo earlier flow.
Let \((G,c,s,t)\) be a finite directed network with source \(s\), sink \(t\), and nonnegative capacities. For a current feasible flow \(f\), the residual network has a residual arc \(u\to v\) whenever the residual capacity from \(u\) to \(v\) is positive. Sending flow along a residual arc increases the flow on its corresponding original arc; using a reverse residual arc decreases that flow. If an opposite-direction residual arc already exists, the corresponding residual capacities are combined.
Suppose \(t\) is reachable, and let \(P\) be a shortest residual path from \(s\) to \(t\). Its length is the number of arcs in the path. The bottleneck is the least residual capacity of its arcs; augmenting by that positive amount decreases the residual capacity on each forward path arc and increases the residual capacity on its reverse arc. The resulting residual network is denoted \(R'\), while the old one is \(R\). Write \(d(v)\) for distances in \(R\) and \(d'(v)\) for distances in \(R'\).
Two Facts About Shortest Paths
First, every prefix of \(P\) is a shortest path from \(s\) to its endpoint. If a prefix ending at \(v_i\) were not shortest, replacing it by a shorter path and then following the rest of \(P\) would give a shorter walk from \(s\) to \(t\). Removing any repeated-vertex portions of that walk would give a path no longer than the walk, contradicting the choice of \(P\). Thus, when \(P=v_0v_1\cdots v_L\), with \(v_0=s\), we have \(d(v_i)=i\).
Second, for every old residual arc \(x\to y\) with \(d(x)\) finite, appending that arc to a shortest path to \(x\) gives a walk to \(y\) of length \(d(x)+1\). Hence \(d(y)\le d(x)+1\). This inequality will also hold for every newly available reverse arc, for a reason specific to shortest-path augmentation.
Proof. Let \(P=v_0v_1\cdots v_L\), where \(v_0=s\). By the prefix property, \(d(v_i)=i\) for each \(i\). An arc in \(R'\) is either an old residual arc that remains after augmentation, or a reverse arc \(v_{i+1}\to v_i\) made available by augmenting along the path. (A reverse arc may already have been present; that does not change the argument.)
For any old arc \(x\to y\) with \(d(x)\) finite, the distance inequality above gives \(d(y)\le d(x)+1\). For any newly available reverse arc \(v_{i+1}\to v_i\), the prefix property gives \(d(v_{i+1})=i+1\) and \(d(v_i)=i\). Therefore \(d(v_i)\le d(v_{i+1})+1\). So every arc \(x\to y\) in \(R'\) whose tail has finite old distance satisfies \(d(y)\le d(x)+1\).
We also need to account for old distance \(\infty\). Every vertex on \(P\) had finite old distance. An old residual arc from a vertex with finite old distance leads to another vertex with finite old distance. A newly available reverse arc has both endpoints on \(P\), so both endpoints also had finite old distance. It follows, by following any path in \(R'\) from \(s\), that all its vertices had finite old distance. In particular, a vertex with old distance \(\infty\) is not newly reachable.
Now take any vertex \(v\) with finite new distance, and choose a shortest path \(s=w_0,w_1,\ldots,w_k=v\) in \(R'\). We have \(d(w_0)=0\). Applying the arc inequality successively gives \(d(w_j)\le j\) for \(0\le j\le k\): if \(d(w_j)\le j\), then \(d(w_{j+1})\le d(w_j)+1\le j+1\). Hence \(d(v)\le k=d'(v)\). Vertices with old distance \(\infty\) remain unreachable, as shown above. This proves \(d'(v)\ge d(v)\) for every vertex. \(\square\)
Worked Augmentations
Worked Example: A Sink Moves Farther Away
Let the directed network have vertex set \(V=\{s,a,b,c,t\}\) and arcs with capacities \(s\to a:2\), \(a\to t:1\), \(s\to b:1\), \(b\to c:1\), and \(c\to t:1\). Start with zero flow on every arc. The paths from \(s\) to \(t\) have lengths \(2\) along \(s\to a\to t\) and \(3\) along \(s\to b\to c\to t\), so the first is shortest.
| Step | Calculation | Result |
|---|---|---|
| Old distances | From \(s\), then \(a,b\), then \(c,t\) | \(d(s)=0,\ d(a)=1,\ d(b)=1,\ d(c)=2,\ d(t)=2\) |
| Bottleneck | \(\min(2,1)=1\) on \(s\to a\to t\) | Augment by \(1\) |
| Updated path arcs | \(s\to a:2-1=1;\ a\to t:1-1=0\) | \(a\to t\) disappears |
| Created reverse arcs | \(a\to s:0+1=1;\ t\to a:0+1=1\) | Both have positive residual capacity |
| New distances | Reach \(a,b\) in \(1\) arc, \(c\) in \(2\), \(t\) in \(3\) | \(d'(t)=3\) |
After the augmentation, the residual path \(s\to b\to c\to t\) remains, and its length is \(3\). The new arc \(t\to a\) points from a vertex at old distance \(2\) to one at old distance \(1\); it cannot provide a shortcut from \(s\) to \(t\). The old distance to \(t\) was \(2\), and the new distance is \(3\), as the theorem permits.
Check: The only positive-capacity residual arcs are \(s\to a\), \(a\to s\), \(s\to b\), \(b\to c\), \(c\to t\), and \(t\to a\). From \(s\), \(a\) and \(b\) are one arc away, \(c\) is two arcs away, and \(t\) is three arcs away. These distances agree with the table.
Worked Example: A New Reverse Arc Is Actually Used
Let \(V=\{s,a,b,c,t\}\), with directed arcs \(s\to a\), \(a\to b\), \(b\to t\), \(s\to c\), and \(c\to b\), each of capacity \(1\). Initially, the two source-to-sink paths \(s\to a\to b\to t\) and \(s\to c\to b\to t\) both have length \(3\). Choose \(P=s\to a\to b\to t\) as the shortest path for this augmentation.
| Step | Calculation | Result |
|---|---|---|
| Old distances | \(a,c\) are reached in \(1\) arc; \(b\) in \(2\); \(t\) in \(3\) | \(d(a)=1,\ d(c)=1,\ d(b)=2,\ d(t)=3\) |
| Bottleneck | \(\min(1,1,1)=1\) on \(P\) | Augment by \(1\) |
| Forward residual capacities | Each of \(s\to a,\ a\to b,\ b\to t\) changes from \(1\) to \(0\) | These arcs disappear |
| Reverse residual capacities | \(a\to s,\ b\to a,\ t\to b\) each change from \(0\) to \(1\) | These arcs become available |
| New distances | \(c\) is at \(1\), \(b\) at \(2\), \(a\) at \(3\); \(t\) is unreachable | \(d'(a)=3,\ d'(t)=\infty\) |
In particular, the new reverse arc \(b\to a\) is used by the residual path \(s\to c\to b\to a\), of length \(3\). This gives a route to \(a\), but not a shorter one: its old distance was \(1\). The sink is now unreachable because the only original arcs entering it were \(b\to t\), which was saturated, and the newly available arc \(t\to b\) points out of the sink.
Check: The positive residual arcs after augmentation are \(s\to c\), \(c\to b\), \(b\to a\), \(a\to s\), and \(t\to b\). Starting at \(s\), the successive reachable sets are \(\{s\}\), then \(\{c\}\), then \(\{b\}\), then \(\{a\}\). No positive residual arc leaves these reachable vertices for \(t\), so \(d'(t)=\infty\).
Worked Example: Unreachable Vertices Stay Unreachable
Let \(V=\{s,x,t,z\}\), with directed arcs \(s\to x\) of capacity \(3\) and \(x\to t\) of capacity \(2\). Vertex \(z\) has no incident arcs. Start with zero flow. The unique source-to-sink path \(s\to x\to t\) has length \(2\).
| Step | Calculation | Result |
|---|---|---|
| Old distances | \(s\) is the source; \(x\) follows in \(1\) arc and \(t\) in \(2\) | \(d(s)=0,\ d(x)=1,\ d(t)=2,\ d(z)=\infty\) |
| Bottleneck | \(\min(3,2)=2\) | Augment by \(2\) |
| Updated residual capacities | \(s\to x:3-2=1;\ x\to t:2-2=0\) | \(x\to t\) disappears |
| Created reverse capacities | \(x\to s:0+2=2;\ t\to x:0+2=2\) | Both reverse arcs are available |
| New distances | \(x\) remains one arc from \(s\); no residual path reaches \(t\) or \(z\) | \(d'(x)=1,\ d'(t)=d'(z)=\infty\) |
Check: The positive residual arcs are \(s\to x\), \(x\to s\), and \(t\to x\). The only one leaving \(s\) is \(s\to x\), and neither \(t\) nor \(z\) is reachable from \(x\). Thus the new distances are exactly those stated; in particular, both old and new distances to \(z\) are \(\infty\).
Common Pitfall: Forgetting Reverse Arcs
A tempting but incorrect argument is that augmentation only deletes saturated forward arcs, so every residual path after augmentation must already have existed. This omits the reverse arcs, which can create new paths. In the second example, omitting \(b\to a\) would incorrectly claim that \(a\) is unreachable after augmentation. In fact, \(s\to c\to b\to a\) is a residual path of length \(3\). The theorem does not say that distances stay the same or that reachability is unchanged; it says only that distances cannot decrease.
The correct proof checks both types of residual arcs. A surviving old arc obeys the old distance inequality because it was already present. A new reverse arc goes from \(v_{i+1}\) back to \(v_i\) on the shortest path, where the old distances are \(i+1\) and \(i\). That direction moves toward a smaller old distance, so it cannot violate the inequality needed to rule out a shorter new path from \(s\).
Check Your Understanding
For each question, distinguish finite distances from \(\infty\), and use the direction of each residual arc.
- Why does every prefix of a shortest residual source-to-sink path have to be shortest to its endpoint?
- If \(P=v_0v_1v_2v_3\) is shortest, what are the old distances of \(v_2\) and \(v_3\), and what inequality does the new reverse arc \(v_3\to v_2\) satisfy?
- Can augmentation make a previously unreachable vertex reachable from \(s\)? Explain why or why not.
- In the first worked example, calculate the bottleneck and the new distance to \(t\) directly from the residual arcs.
- Why does the theorem allow a vertex’s distance to increase or become \(\infty\), even though it forbids a decrease?