Max-Flow Min-Cut Algorithm

Max-Flow-Min-Cut ( graph G = ( V, E ), source S, terminal T, capacity C )

   1.   f := 0 (flow 0 on all edges)

   2.   opt := false

   3.   WHILE not opt DO

   3a.       construct the residual graph G_f

   3b.       find a directed path P from S to T in G_f (an augmenting path)

   3c.       IF such an augmenting path P exists

   3d.           THEN update flow f along P

   3e.           ELSE set opt := true; and X := the set of vertices in G_f reachable from S

   4.  END-WHILE

   5.  return f as the max flow, and ( X , V-X ) as the min-cut

   END