# Network flow problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Network_flow_problem
> Markdown URL: https://mediated.wiki/source/Network_flow_problem.md
> Source: https://en.wikipedia.org/wiki/Network_flow_problem
> Source revision: 1296770911
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Class of computational problems

In [combinatorial optimization](/source/Combinatorial_optimization), **network flow problems** are a class of computational problems in which the input is a [flow network](/source/Flow_network) (a graph with numerical capacities on its edges), and the goal is to construct a [flow](/source/Flow_network#Flows), 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.[1]

Specific types of network flow problems include:

- The [maximum flow problem](/source/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[1]: 166–206

- The [minimum-cost flow problem](/source/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[1]: 294–356

- The [multi-commodity flow problem](/source/Multi-commodity_flow_problem), in which one must construct multiple flows for different commodities whose total flow amounts together respect the capacities[1]: 649–694

- [Nowhere-zero flow](/source/Nowhere-zero_flow), a type of flow studied in combinatorics in which the flow amounts are restricted to a [finite set](/source/Finite_set) of nonzero values

The [max-flow min-cut theorem](/source/Max-flow_min-cut_theorem) equates the value of a maximum flow to the value of a [minimum cut](/source/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](/source/Approximate_max-flow_min-cut_theorem) provide an extension of this result to multi-commodity flow problems. The [Gomory–Hu tree](/source/Gomory%E2%80%93Hu_tree) of an undirected flow network provides a concise representation of all minimum cuts between different pairs of terminal vertices.

[Algorithms](/source/Algorithm) for constructing flows include

- [Dinic's algorithm](/source/Dinic's_algorithm), a strongly polynomial algorithm for maximum flow[1]: 221–223

- The [Edmonds–Karp algorithm](/source/Edmonds%E2%80%93Karp_algorithm), a faster strongly polynomial algorithm for maximum flow

- The [Ford–Fulkerson algorithm](/source/Ford%E2%80%93Fulkerson_algorithm), a [greedy algorithm](/source/Greedy_algorithm) for maximum flow that is not in general strongly polynomial

- The [network simplex algorithm](/source/Network_simplex_algorithm), a method based on linear programming but specialized for network flow[1]: 402–460

- The [out-of-kilter algorithm](/source/Out-of-kilter_algorithm) for minimum-cost flow[1]: 326–331

- The [push–relabel maximum flow algorithm](/source/Push%E2%80%93relabel_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](/source/Linear_program) or similar and solved using a general purpose optimization solver.

## References

1. ^ [***a***](#cite_ref-FNbook_1-0) [***b***](#cite_ref-FNbook_1-1) [***c***](#cite_ref-FNbook_1-2) [***d***](#cite_ref-FNbook_1-3) [***e***](#cite_ref-FNbook_1-4) [***f***](#cite_ref-FNbook_1-5) [***g***](#cite_ref-FNbook_1-6) Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). *Network Flows: Theory, Algorithms, and Applications*. Prentice Hall.

Index of articles associated with the same name

This [set index article](https://en.wikipedia.org/wiki/Wikipedia:Set_index_articles) includes a list of related items that share the same name (or similar names).
 If an [internal link](https://en.wikipedia.org/w/index.php?title=Special:Whatlinkshere/Network_flow_problem&namespace=0) incorrectly led you here, you may wish to change the link to point directly to the intended article.

---
Adapted from the Wikipedia article [Network flow problem](https://en.wikipedia.org/wiki/Network_flow_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Network_flow_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.