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 does so using a residual graph, a clone of the original graph G with augmented edges indicating flow. Thus, the overall algorithm, the Ford-Fulkerson algorithm, combines an two different functions. One for augmenting an edge, and another for computing overall flow:

  Augment(f, P)
  b=bottleneck(P, f)
  for each edge in P
      if e=(u,v) is a forward edge then
          increase f(e) in G by b
      else e is a backward edge and e=(v,u)
          decrease f(e) in G by b
   return(f)
   

The overall algorithm is O(m). The overall readability of the section was 6/10.