一个网络最大流的例子。源点为 s ，汇点为 t 。数字表示流和容量。 在优化理论中，最大流问题 （英語：Maximum flow problem ）涉及到在一个单源点、单汇点的网络流 中找到一条最大的流。
最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理 。
最大流问题最早是在1954年由泰德·哈里斯 [ 1] [ 2] [ 3] 小萊斯特·倫道夫·福特 和德爾伯特·雷·富爾克森 创建了第一个已知的算法，福特-富爾克森算法 。[ 4] [ 5]
多年来，最大流问题的各种改进算法被发现，例如傑克·埃德蒙茲 理查德·卡普 和葉菲姆·迪尼茨 最短增广路算法 ；迪尼茨的阻塞流算法 ；安德魯·V·戈德堡 羅伯特·塔揚 的Push-Relabel算法；戈德堡和Rao的binary阻塞流算法；Christiano、Kelner和亞歷山大·馬德瑞（Aleksander Madry）的电流算法；Spielman发现一个最大流近似最优解，但仅适用于无向图。[ 6] [ 7]
一个网络流，源点为 s，汇点为 t。边上的数字为容量。 设
N
=
(
V
,
E
)
{\displaystyle N=(V,E)}
s
{\displaystyle s}
t
{\displaystyle t}
N
{\displaystyle N}
s
,
t
∈
V
{\displaystyle s,t\in V}
一个边的容量 为映射
c
:
E
→
R
+
{\displaystyle c:E\to \mathbb {R} ^{+}}
c
u
v
{\displaystyle c_{uv}}
c
(
u
,
v
)
{\displaystyle c(u,v)}
一个流 为一个映射
f
:
E
→
R
+
{\displaystyle f:E\to \mathbb {R} ^{+}}
f
u
v
{\displaystyle f_{uv}}
f
(
u
,
v
)
{\displaystyle f(u,v)}
对于每个
(
u
,
v
)
∈
E
{\displaystyle (u,v)\in E}
f
u
v
≤
c
u
v
{\displaystyle f_{uv}\leq c_{uv}}
对于每个
v
∈
V
∖
{
s
,
t
}
{\displaystyle v\in V\setminus \{s,t\}}
∑
u
:
(
u
,
v
)
∈
E
f
u
v
=
∑
u
:
(
v
,
u
)
∈
E
f
v
u
{\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}}
流量 定义为
|
f
|
=
∑
v
:
(
s
,
v
)
∈
E
f
s
v
{\displaystyle |f|=\sum _{v:(s,v)\in E}f_{sv}}
s
{\displaystyle s}
N
{\displaystyle N}
最大流问题 就是最大化
|
f
|
{\displaystyle |f|}
s
{\displaystyle s}
t
{\displaystyle t}
算法
复杂度
描述
线性规划
福特-富爾克森算法
O (E max| f |)
埃德蒙兹-卡普算法
O (VE 2 )福特-富爾克森算法的特例，使用广度优先搜索 寻找增广路径.
迪尼茨阻塞流算法
O (V 2 E )
MPM (Malhotra, Pramodh-Kumar and Maheshwari)算法[ 8]
O (V 3 )只适用于无环图。参考 Original Paper .
Dinic算法
O (VE log(V ))
push-relabel maximum flow算法
O (V 2 E )
Push-relabel算法，使用FIFO vertex selection rule
O (V 3 )
Push-relabel算法，使用 dynamic trees
O
(
V
E
log
V
2
E
)
{\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}
KRT (King, Rao, Tarjan)算法[ 9]
O
(
E
V
log
E
V
log
V
V
)
{\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}
Binary阻塞流算法[ 10]
O
(
E
⋅
min
(
V
2
3
,
E
)
⋅
log
V
2
E
log
U
)
{\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]
O
(
V
E
)
{\displaystyle O(VE)}
Orlin's algorithm （页面存档备份 ，存于互联网档案馆 ） solves max-flow in O (VE )
E
≤
O
(
V
16
15
−
ϵ
)
{\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}
O (VE )
E
>
V
1
+
ϵ
{\displaystyle E>V^{1+\epsilon }}
^ Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259 ^ 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-2doi:10.1007/0-387-25837-X_5 ^ 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）. ^ 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 ^ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks , Princeton University Press (1962).
^ 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. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF) . 2014: 217. ISBN 978-1-61197-338-9arXiv:1304.2338 doi:10.1137/1.9781611973402.16 原始内容 (PDF) 存档于2016-03-03）. ^ Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem . MIT News. 7 January 2014 [8 January 2014] . （原始内容存档 于2014-02-26）. ^ Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. An
O
(
|
V
|
3
)
{\displaystyle O(|V|^{3})}
7 (6): 277–278. doi:10.1016/0020-0190(78)90016-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 ^ Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊 . 1998, 45 (5): 783. doi:10.1145/290179.290181 ^ 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
