Ford-fulkerson max-fow algorithm Algorithm: flu,v <0 for while an augmenting path p in G wrtf exists do augment f by cr(p) Can be slow 2:10 1:109 1:109 2:10 2 billion iterations on a graph with 4 vertices! c 2001 by Charles E Leiserson Introduction to Agorithms Day40L23.12© 2001 by Charles E. Leiserson Introduction to Algorithms Day 40 L23.12 Ford-Fulkerson max-flow algorithm Can be slow: ss tt 2:109 1:109 2:109 1:1 1:109 G: 2 billion iterations on a graph with 4 vertices! Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by cf(p)