Cover by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

Maximum Flow

Given a flow network, it is possible to compute the maximum flow (mf) between vertices s and t given the capacity constraints c(u,v)≥0 for all directed edges e=(u,v) in E. That is, compute the largest amount that can flow out of source s, through the network, and into sink t given specific capacity limits on individual edges. Starting with a feasible flow (a flow of 0 through every edge is feasible), Ford-Fulkerson (Figure 8-3) successively locates an augmenting path through the network from s to t to which more flow can be added. The algorithm terminates when no augmenting paths can be found. The Max-flow Min-cut theorem (Ford-Fulkerson, 1962) guarantees that with non-negative flows and capacities, Ford-Fulkerson always terminates and identifies the maximum flow in a network.

Ford-Fulkerson fact sheet

Figure 8-3. Ford-Fulkerson fact sheet

Input/Output

In this presentation, we describe Ford-Fulkerson using linked lists to store edges. Each vertex u maintains two separate lists: forward edges for the edges emanating from u and backward edges for the edges coming into u; thus each edge appears in two lists, doubling the total storage. The code repository provided with this book contains an implementation using a two-dimensional matrix to store edges, a more appropriate data structure to use for dense flow network graphs.

Input

The flow network is defined by a graph G=(V, E) with designated start ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required