Network flow problem

---

title: "Network flow problem" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["network-flow-problem", "graph-algorithms", "combinatorial-optimization", "directed-graphs"] description: "Class of computational problems" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/Network_flow_problem" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Class of computational problems ::

In combinatorial optimization, network flow problems are a class of computational problems in which the input is a flow network (a graph with numerical capacities on its edges), and the goal is to construct a flow, numerical values on each edge that respect the capacity constraints and that have incoming flow equal to outgoing flow at all vertices except for certain designated terminals.{{Cite book | last1 = Ahuja | first1 = Ravindra K. | last2 = Magnanti | first2 = Thomas L. | last3 = Orlin | first3 = James B. | title = Network Flows: Theory, Algorithms, and Applications | publisher = Prentice Hall | year = 1993

Specific types of network flow problems include:

• The maximum flow problem, in which the goal is to maximize the total amount of flow out of the source terminals and into the sink terminals
• The minimum-cost flow problem, in which the edges have costs as well as capacities and the goal is to achieve a given amount of flow (or a maximum flow) that has the minimum possible cost
• The multi-commodity flow problem, in which one must construct multiple flows for different commodities whose total flow amounts together respect the capacities
• Nowhere-zero flow, a type of flow studied in combinatorics in which the flow amounts are restricted to a finite set of nonzero values

The max-flow min-cut theorem equates the value of a maximum flow to the value of a minimum cut, a partition of the vertices of the flow network that minimizes the total capacity of edges crossing from one side of the partition to the other. Approximate max-flow min-cut theorems provide an extension of this result to multi-commodity flow problems. The Gomory–Hu tree of an undirected flow network provides a concise representation of all minimum cuts between different pairs of terminal vertices.

Algorithms for constructing flows include

• Dinic's algorithm, a strongly polynomial algorithm for maximum flow
• The Edmonds–Karp algorithm, a faster strongly polynomial algorithm for maximum flow
• The Ford–Fulkerson algorithm, a greedy algorithm for maximum flow that is not in general strongly polynomial
• The network simplex algorithm, a method based on linear programming but specialized for network flow
• The out-of-kilter algorithm for minimum-cost flow
• The push–relabel maximum flow algorithm, one of the most efficient known techniques for maximum flow

Otherwise the problem can be formulated as a more conventional linear program or similar and solved using a general purpose optimization solver.

References

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::