Algorithms
Advanced Graph Algorithms (Network Flow)
Difficulty: Advanced
Two seemingly different problems, the maximum amount of water you can push from a source to a sink through a network of capacitated pipes, and the minimum total capacity you must remove to disconnect the sink from the source, turn out to...
Advanced Graph Algorithms (Network Flow)
Two seemingly different problems, the maximum amount of water you can push from a source to a sink through a network of capacitated pipes, and the minimum total capacity you must remove to disconnect the sink from the source, turn out to have the same answer for every graph. The max-flow min-cut theorem ties them together, and once you accept it a surprising number of optimization problems (image segmentation, project selection, bipartite matching) collapse into max-flow instances.
Advanced Graph Algorithms (Network Flow) introduces the algorithms that compute that maximum flow. You will work through the Ford-Fulkerson method built on augmenting paths and the residual graph, the BFS-based Edmonds-Karp variant with its O(V * E^2) guarantee, and Dinic's algorithm which uses level graphs and blocking flows to reach O(V^2 * E). The lesson then turns to maximum bipartite matching (Hungarian and Hopcroft-Karp), applications like airline scheduling and image segmentation, and a first look at minimum-cost flow.
In Graph Algorithms (Advanced), you handled MST, all-pairs shortest paths, and SCCs on edge-weighted graphs. Network flow keeps the weighted-edge model but flips the question from "shortest" to "highest throughput."
Next, String Algorithms turns to pattern matching, the implicit automaton of a regular expression.
Prerequisites:
Graph Algorithms (Advanced)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the max-flow min-cut theorem and how it connects maximum flow to minimum cut.
Implement the Ford-Fulkerson method using BFS (Edmonds-Karp) and explain residual graphs and augmenting paths.
Describe Dinic's algorithm and its improvement over Edmonds-Karp using level graphs and blocking flows.
Solve maximum bipartite matching by reducing it to a max-flow problem.
Identify real-world problems that reduce to network flow (project selection, airline scheduling, image segmentation).
Analyze the time complexity of Ford-Fulkerson, Edmonds-Karp, and Dinic's algorithms.
Why This Matters
01
The max-flow min-cut theorem is one of the most elegant results in combinatorial optimization, connecting seemingly different problems — maximum flow and minimum cut.
02
Network flow algorithms solve maximum bipartite matching, which has applications in job assignment, resource allocation, and scheduling problems.
03
Edmonds-Karp guarantees O(V * E^2) performance regardless of capacity values, avoiding the integer-capacity dependency of basic Ford-Fulkerson.
04
Many optimization problems (project selection, image segmentation, minimum vertex cover in bipartite graphs) reduce to max-flow, making it a powerful problem-solving tool.
Key Terms
8 terms you'll encounter in this lesson
Flow Network
A directed graph where each edge has a non-negative capacity. Flow must satisfy: (1) capacity constraint — flow on edge <= capacity, (2) conservation — flow in = flow out at every non-source/sink vertex.
Residual Graph
A graph derived from the flow network showing remaining capacity. For each edge with flow f and capacity c: residual capacity = c - f (forward), and a reverse edge with capacity f allows 'undoing' flow.
Augmenting Path
A path from source to sink in the residual graph with positive residual capacity on every edge. Each augmenting path increases the total flow.
Max-Flow Min-Cut Theorem
The maximum flow from source to sink equals the minimum capacity of any cut separating source from sink. A cut is a partition (S, T) where source is in S and sink is in T.
Ford-Fulkerson Method
Repeatedly find augmenting paths in the residual graph and push flow along them until no augmenting path exists. The method is correct by the max-flow min-cut theorem.
Edmonds-Karp Algorithm
Ford-Fulkerson using BFS to find augmenting paths. BFS guarantees shortest augmenting paths, giving O(V * E^2) time complexity independent of capacity values.
Dinic's Algorithm
An improvement over Edmonds-Karp that constructs a level graph (BFS layers) and finds blocking flows (saturating at least one edge per path). Time: O(V^2 * E).
Bipartite Matching
Finding the maximum number of non-overlapping edges between two disjoint vertex sets. Reduces to max-flow by adding a super source and super sink with unit capacities.
Heads Up
Common misconceptions to watch out for
"Ford-Fulkerson always terminates"
With irrational capacities, Ford-Fulkerson using DFS may not terminate or may converge to the wrong answer. Edmonds-Karp (using BFS) always terminates in O(V * E^2) regardless of capacity values.
"The residual graph only has forward edges"
The residual graph includes both forward edges (remaining capacity) and reverse edges (used flow). Reverse edges are essential — they allow the algorithm to 'undo' flow decisions and reroute flow along better paths.
"Max-flow and min-cut are different problems"
The max-flow min-cut theorem proves they are equivalent: the maximum flow from s to t equals the minimum cut capacity separating s from t. Solving one solves the other.
"Bipartite matching requires a specialized algorithm"
Maximum bipartite matching can be solved by reducing to max-flow: add a source connected to all left vertices and a sink connected to all right vertices, all with capacity 1. The max-flow equals the maximum matching.