Question

You are given a flow network G with n >4 vertices. Besides the source sand the sink t, you are also given two other special vertices u and v belonging to G. Describe an algorithm which finds a cut of the smallest possible capacity among all cuts in which vertex u is at the same side of the cut as the sources and vertex v is at the same side as sink t.

Hint: it is enough to ad two edges, but students often prefer to add a super source and a super sink

Answer 1

Ford-Fulkerson augmenting path algorithm.
・Start with f(e) = 0 for all edge e ∈ E.
・Find an augmenting path P in the residual graph Gf .
・Augment flow along path P.
・Repeat until you get stuck.
19
Ford-Fulkerson algorithm
FORD-FULKERSON (G, s, t, c)

FOREACH edge e ∈ E : f(e) ← 0.
Gf ← residual graph.
WHILE (there exists an augmenting path P in Gf )
f ← AUGMENT (f, c, P).
Update Gf.
RETURN f.
}