Flow networks and flows
A flow network G = (V, E) is a directed graph in which each edge (u, v) ∈E has a nonnegative capacity c(u, v) ≥ 0. If (u, v) ∉ E, we assume that c(u, v) = 0. We distinguish two vertices in a flow network: a source s and a sink t. We are now ready to define flows more formally. Let G = (V, E) be a flow network with a capacity function c. Let s be the source of the network, and let t be the sink. A flow in G is a real-valued function f : V × V → R that satisfies the following three properties:Capacity constraint: For all u, v ∈ V, we require f (u, v) ≤ c(u, v).
Skew symmetry: For all u, v ∈ V, we require f (u, v) = - f (v, u).
Flow conservation: For all u ∈ V - {s, t}, we require
The Ford-Fulkerson method FORD-FULKERSON-METHOD(G, s, t) 1 initialize flow f to 0 2 while there exists an augmenting path p 3 do augment flow f along p 4 return f FORD-FULKERSON(G, s, t) 1 for each edge (u, v) ∈ E[G] 2 do f[u, v] ← 0 3 f[v, u] ← 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) ← min {cf(u, v) : (u, v) is in p} 6 for each edge (u, v) in p 7 do f[u, v] ← f[u, v] + cf(p) 8 f[v, u] ← -f[u, v]