Chapter 7

For our purposes, we define a flow network as a graph G with a source node s and a sink node t with each edge e having a non-negative capacity ce. There are also two important conditions: the capacity condition and the conservation condition. The capacity condition restricts a flow of an edge to be less than or equal to its capacity. The conservation condition assures that, with the exception of the source and sink nodes, the flow into a node v equals the flow out of v. Thus, our problem is to maximize the flow within a flow network. The algorithm that achieves this