networkflow

Network flow is a field of study in combinatorial optimization that analyzes the movement of a commodity through a network. The network is modeled as a directed graph with nonnegative edge capacities, and two distinguished nodes: a source and a sink. A flow assigns to each edge a nonnegative quantity representing how much of the commodity traverses that edge, subject to capacity constraints and the conservation of flow at every intermediate node (the total inflow equals the total outflow for non-terminal nodes). The central problem is to determine the maximum feasible flow from the source to the sink, known as the maximum-flow problem.

A fundamental result is the max-flow min-cut theorem, which states that the maximum flow value equals the minimum total capacity of an s-t cut, establishing a dual relationship between flows and cuts. Classic algorithms include the Ford–Fulkerson method, which augments along residual paths; Edmonds–Karp, which implements shortest augmenting paths via breadth-first search and runs in polynomial time; and Dinic’s algorithm, which uses layered networks to achieve faster performance on many instances. In networks with integer capacities, the maximum flow is also integral.

Variants of network flow address broader scenarios. Multi-commodity flow considers several different supplies and demands sharing the same network; dynamic and stochastic flow models incorporate time-varying capacities and uncertainty. The theory of network flow underpins many practical methods in operations research and has connections to problems such as bipartite matching, scheduling, and network design.

Applications span telecommunications and data networks (routing and resource allocation), transportation and logistics (traffic assignment and supply chains), and computer vision (image segmentation via max-flow/min-cut). The field originates from the work of Ford and Fulkerson in the 1950s and has since developed into a rich set of models, algorithms, and applications.