Source code online books for professionals by professionals

Figure 10-2.  An s-t network with one path found (heavy edges) and one augmenting path (highlighted)
The principle of canceling works just like in bipartite matching. As we search for an augmenting path, we move 
from s to a and then to b. There, we’re blocked by the edge bt. The problem at this point is that b has two incoming 
paths from a and c but only one outgoing path. By canceling the edge cb, we’ve solved the problem for b, but now 
there’s a problem at c. This is the same kind of cascade effect we saw for the bipartite matching. In this case, c has an 
incoming path from s, but no outgoing path—we need to find somewhere for the path to go. We do that by continuing 
our path via d to t, as shown by the highlights in Figure 
10-2
.
If you either add an incoming edge or cancel an outgoing one at some node u, that node will be overcrowded.  
It will have more paths entering than leaving, which isn’t allowed. You can fix this either by adding an outgoing edge 
or by canceling an incoming one. All in all, this works out to finding a path from s, following unused edges in their 
direction and used ones against their direction. Any time you can find such an augmenting path, you will also have 
discovered an additional disjoint path.
Listing 10-2 shows code for implementing this algorithm. As before, the code for the tr function can be found in 
Listing 5-10.

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
214