Skip to main content

Maximum Flow

Learn Maximum Flow (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Maximum Flow: Edmonds-Karp The maximum flow problem asks how much can be sent from s to t. Ford-Fulkerson repeats find an augmenting path, push its bottleneck until none is left. Edmonds-Karp always chooses the shortest path (by BFS), which guarantees at most V·E augmentations and a total of O(V·E²) . The max-flow min-cut theorem : the value of the maximum flow equals the capacity of the smallest cut separating s from t.

More lessons in Graphs