最大流问题

在优化理论中，最大流问题（英語：Maximum flow problem）涉及到在一个单源点、单汇点的网络流中找到一条最大的流。

一个网络最大流的例子。源点为 s，汇点为 t。数字表示流和容量。

最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理。

历史

最大流问题最早是在1954年，由T.E.Harris 和F.S.Ross通过一个苏联铁路的交通流量的简化模型提出的。^[1][2][3] 1955年，L.R. Ford, Jr.和D.R. Fulkerson创建了第一个已知的算法， Ford–Fulkerson算法。^[4][5]

多年来，最大流问题的各种改进算法被发现，例如Edmonds和Karp还有Dinitz的最短增广路算法；Dinitz的阻塞流算法； Goldberg和陶尔扬的Push-Relabel算法；Goldberg和Rao的binary阻塞流算法。 Christiano, Kelner, Madry的电流算法，Spielman 发现一个最大流近似最优解，但仅适用于无向图。^[6][7]

定义

 

一个网络流，源点为 s，汇点为 t。边上的数字为容量。

设${\displaystyle N=(V,E)}$ 为一个网络，其中${\displaystyle s}$ 和${\displaystyle t}$ 分别是${\displaystyle N}$ 的源点和汇点（${\displaystyle s,t\in V}$ ）。

一个边的容量为映射${\displaystyle c:E\to \mathbb {R} ^{+}}$ ，记为${\displaystyle c_{uv}}$ 或${\displaystyle c(u,v)}$ 。它表示可以通过一条边的流量的最大值。

一个流为一个映射${\displaystyle f:E\to \mathbb {R} ^{+}}$ ，记为${\displaystyle f_{uv}}$ 或${\displaystyle f(u,v)}$ ，遵循下面两个限制：

1. 对于每个${\displaystyle (u,v)\in E}$ ，有${\displaystyle f_{uv}\leq c_{uv}}$ （即容量限制：一个边的流量不能超过它的容量）；
2. 对于每个${\displaystyle v\in V\setminus \{s,t\}}$ ，有${\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}}$ （即流的保留：流入一个节点的流的总和必须等于流出这个节点的流的总和，源点和汇点除外）。

流量定义为 ${\displaystyle |f|=\sum _{v:(s,v)\in E}f_{sv}}$ ，其中${\displaystyle s}$ 为${\displaystyle N}$ 的源点，它表示从源点到汇点的流的数量。

最大流问题就是最大化${\displaystyle |f|}$ ，即从${\displaystyle s}$ 点到${\displaystyle t}$ 点尽可能规划最大的流量。

解法

算法	复杂度	描述
线性规划
Ford–Fulkerson算法	O(E max| f |)
Edmonds–Karp算法	O(VE^2)	Ford–Fulkerson算法的特例，使用广度优先搜索寻找增广路径.
Dinic阻塞流算法	O(V^2E)
MPM (Malhotra, Pramodh-Kumar and Maheshwari)算法^[8]	O(V^3)	只适用于无环图。参考 Original Paper.
Dinic算法	O(VE log(V))
push-relabel maximum flow算法	O(V^2E)
Push-relabel算法，使用FIFO vertex selection rule	O(V^3)
Push-relabel算法，使用 dynamic trees	${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$
KRT (King, Rao, Tarjan)算法^[9]	${\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}$
Binary阻塞流算法^[10]	${\displaystyle O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)}$
James B Orlin's + KRT (King, Rao, Tarjan)算法^[11]	${\displaystyle O(VE)}$	Orlin's algorithm （页面存档备份，存于互联网档案馆） solves max-flow in O(VE) time for ${\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}$  while KRT solves it in O(VE) for ${\displaystyle E>V^{1+\epsilon }}$ .

参考文献

1. Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259. 
2. Gass, Saul I.; Assad, Arjang A. Mathematical, algorithmic and professional developments of operations research from 1951 to 1956. An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science 75. 2005: 79–110. ISBN 1-4020-8116-2. doi:10.1007/0-387-25837-X_5. 
3. Harris, T. E.; Ross, F. S. Fundamentals of a Method for Evaluating Rail Net Capacities (PDF). Research Memorandum (Rand Corporation). 1955 [2017-03-07]. （原始内容 (PDF)于2017-02-17）. 
4. Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5. 
5. Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
6. Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. (PDF). 2014: 217. ISBN 978-1-61197-338-9. arXiv:1304.2338  . doi:10.1137/1.9781611973402.16. （原始内容 (PDF)存档于2016-03-03）. 
7. Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. （原始内容于2014-02-26）. 
8. Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. An ${\displaystyle O(|V|^{3})}$  algorithm for finding maximum flows in networks. Information Processing Letters. 1978, 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9. 
9. King, V.; Rao, S.; Tarjan, R. A Faster Deterministic Maximum Flow Algorithm. Journal of Algorithms. 1994, 17 (3): 447–474. doi:10.1006/jagm.1994.1044. 
10. Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181. 
11. Orlin, James B. Max flows in O(nm) time, or better. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 765–774. doi:10.1145/2488608.2488705.