Chapter 7: Network Flow

In this chapter, we discuss network flow algorithms.

We can use graphs to model flow networks. In these networks, edges have certain capacities that indicate the maximum flow allowed over that edge and nodes represent interchanges that direct the flow to some edge. A source node (s) generates flow, a sink node (t) absorbs it, and all other nodes redirect the flow so that the amount of flow into it is the same as the flow out. We want to find the maximum possible flow we can send through the network.

We can do this using the Ford-Fulkerson algorithm. First we need to create a residual graph. This looks identical to our original graph initially. As we add flow, we decrease the capacity of the original edge (say from u to v) and add a backward edge (from v to u) with capacity equal to the amount of flow currently flowing from u to v. When an edge is at capacity, i.e. the remaining capacity is zero, we remove it from our residual graph, leaving just a backward edge. We need this residual graph with backward edges so that we can undo flow we may not want on a certain edge.

Now we are ready to run the algorithm. We are looking to maximize flow, so we begin with no flow and find an s to t path we can augment in the residual graph. We identify the bottleneck b (capacity of edge of minimum capacity) of this path and then check the edges in the path. If all of the edges were in the original graph, then we can add a flow of b to each edge. If any of the edges were not in the original graph, we still add a flow of b to edges that were in the initial graph but we instead remove a flow of b from those edges that are backward edges. This undoes some of the flow from that edge and pushes it along a different path. We no more paths exist, we are done.