Algorithms, Chapter 10: Maximum Flows & Minimum Cuts
by Jeff Erickson · University of Illinois Urbana-Champaign
Chapter from Erickson's Creative Commons algorithms textbook. Develops flows, cuts, residual graphs, and the max-flow min-cut theorem with careful proofs, then Ford-Fulkerson's non-termination on irrational capacities, Edmonds-Karp variants, and Dinic's algorithm. A companion chapter covers applications.
More resources on Network Flows
Wolfram MathWorld
MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading.
CP-Algorithms - Minimum-cost flow (successive shortest path)
Article explaining the successive shortest path algorithm for minimum-cost flow, an extension of Edmonds-Karp that augments along cheapest paths, covering directed and undirected graphs, complexity analysis, an SPFA-based implementation, and practice problems. Readers can implement min-cost max-flow for contest problems.
Design and Analysis of Algorithms (MIT 6.046J)
Intermediate algorithms after 6.006: divide-and-conquer, randomization, dynamic programming, greedy algorithms, network flow, amortization, complexity and cryptography. 39 lecture videos, notes, problem sets and exams with solutions train learners to design efficient algorithms and prove their correctness and running time.
Lecture 13: Incremental Improvement: Max Flow, Min Cut (MIT 6.046J)
Introduces flow networks, cuts, residual graphs and augmenting paths, proves the max-flow min-cut theorem, and develops the Ford-Fulkerson method and its running time. This single recorded lecture prepares learners to compute maximum flows and minimum cuts in directed graphs.
Maximum Flow: Ford-Fulkerson and Edmonds-Karp
Implementation-focused reference maintained by the competitive programming community. Explains the Ford-Fulkerson method, residual capacities, the integral flow and max-flow min-cut theorems, with working C++ code. Linked sibling pages cover Dinic's algorithm, push-relabel, and minimum-cost flow.
CS261: A Second Course in Algorithms
Stanford's second algorithms course, with free lecture videos and notes. Twenty lectures build from Ford-Fulkerson through Edmonds-Karp, Dinic's blocking flows, push-relabel, minimum s-t cut for image segmentation, bipartite and minimum-cost matching, then linear programming duality and strong duality.