Ford–Fulkerson Algorithm

The Ford-Fulkerson Algorithm is a classic solution for maximum flow problems.

 Let \(G(V,E)\) be a graph. For each edge \((u,v)\), its capacity is \(c(u,v)\) and flow is \(f(u,v)\). We want to find the maximum flow from the source \(s\) to sink \(t\).

We put following constraints on the graph:

  1. Capacity constraints: \(\forall (u,v)\in E\) \( f(u,v)\leq c(u,v)\).
  On any edge, the flow cannot exceed its capacity.

  2. Skew symmetry: \(\forall (u,v)\in E\) \(f(u,v) = -f(v,u)\).
  The net flow over \((u,v)\) must be the opposite of the one over \((v,u)\).

  3. Flow conservation: \(\forall u\in V:u\neq s\cap u\neq t \Rightarrow\sum_{w\in V} f(u,w)=0\).
  For any node other than \(u\) and \(v\), the net flow should be 0.

We also define the residual network over \(G\) as \(G_f(V,E_f)\), where the capacity of edges is \(c_f(u,v)=c(u,v)-f(u,v)\).

The algorithm goes like:

  1.  \(f(u,v)\leftarrow 0\) for all edges \((u,v)\).
  2. While there is a path from \(s\) to \(t\) in \(G_f\), such that \(c_f(u,v)>0\) for all edges \((u,v)\in p\):
      i. Find \(c_f(p)=min\{c_f(u,v):(u,v)\in p\}\).
      ii. For each edge \((u,v)\in p\)
          a. \(f(u,v)\leftarrow f(u,v)+c_f(p)\) (Send the flow along the path)
          b. \(f(v,u)\leftarrow f(v,u)-c_f(p)\) (The flow might be "returned" later)

In step 2, we can use BFS or DFS to find the path.

This algorithm runs in \(O(Ef)\) time, where \(E\) is the number of edges and \(f\) is the maximum flow in the graph.

UPDATE 8/22/12: An interesting theorem that relates to the flow network is the Max-flow Min-cut Theorem. It states
        The maximum value of an s-t flow is equal to the minimum capacity over all s-t cuts.



Reference:
Wikipage on Ford-Fulkerson algorithm
Wikipedia page on Max-flow Min-Cut Theorem