A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Network flow algorithms extend beyond basic Ford-Fulkerson to achieve faster runtimes and solve richer problems. The push-relabel algorithm (Goldberg-Tarjan) achieves O(V2 * E) time for max-flow by maintaining a preflow (allowing excess at vertices) and using height labels to guide flow toward the sink — avoiding the repeated BFS of augmenting-path methods. Dinic's algorithm achieves O(V2 * E) using blocking flows in layered graphs, with O(E * sqrt(V)) for unit-capacity networks. Minimum-cost flow generalizes max-flow by adding edge costs and finding the cheapest way to route a given flow value, solvable via successive shortest paths or cost-scaling in O(V * E * log V * log(VC)). These algorithms reduce to LP but exploit network structure for dramatically faster specialized solutions. Applications span bipartite matching, project selection, image segmentation, and airline scheduling.
You already understand the Ford-Fulkerson framework: find augmenting paths from source to sink, push flow along them, repeat until no augmenting path exists. The advanced algorithms you encounter here improve the runtime by orders of magnitude through deeper structural insights — preflow techniques, layered graph decompositions, and potential function arguments.
Dinic's algorithm introduces the concept of blocking flows on layered graphs. First, BFS from the source constructs a layered graph where each edge goes from layer i to layer i+1 (these are the shortest-path layers). A blocking flow saturates at least one edge on every source-to-sink path in this layered graph, and can be found in O(VE) time. After each blocking flow, the shortest augmenting path length increases by at least 1, so at most V-1 phases suffice. The total work is O(V2 E). On unit-capacity networks, each phase costs only O(E) and the argument about path lengths after sqrt(V) phases reduces the total to O(E sqrt(V)) — this is the Hopcroft-Karp algorithm for bipartite matching.
The push-relabel algorithm (Goldberg and Tarjan, 1988) takes a radically different approach. Instead of finding global augmenting paths, it maintains a preflow — flow that may violate conservation by having excess at non-source/sink vertices — and works locally. Each vertex has a height label; flow is pushed "downhill" (from higher to lower labels). When a vertex has excess but no downhill neighbors, its label is raised (relabeled). The key insight is that the height labels form a valid distance estimate to the sink in the residual graph, so the algorithm implicitly routes excess flow toward the sink. The amortized analysis bounds the total work at O(V2 E), with practical implementations using FIFO or highest-label selection achieving much better empirical performance.
Minimum-cost flow extends the framework by assigning costs to edges and finding the cheapest flow of a given value. The successive shortest paths algorithm repeatedly finds shortest (minimum cost) augmenting paths using Bellman-Ford or Dijkstra with Johnson's reweighting. Cost-scaling algorithms achieve O(V E log V log(VC)) by iteratively refining approximate complementary slackness conditions. Applications include transportation problems, assignment problems, and any optimization where both capacity and cost constraints matter. The LP dual of minimum-cost flow yields the economic interpretation: dual variables are node potentials (prices), and complementary slackness means flow only uses edges where the reduced cost (cost minus potential difference) is optimal.