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