最大流问题

在优化理论中,最大流问题涉及到在一个单源点、单汇点的网络流中找到一条最大的流。

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

历史

最大流问题最早是在1954年，由T.E.Harris 和F.S.Ross通过一个苏联铁路的交通流量的简化模型提出的。1955年，莱斯特*福特小和德尔伯特R.Fulkerson 创建了第一个已知的算法， Ford–Fulkerson算法。

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

定义

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

解法

算法	复杂度	描述
线性规划
Ford–Fulkerson算法	O(E max\| f \|)
Edmonds–Karp算法	O(VE2)	Ford–Fulkerson算法的特例，使用广度优先搜索寻找增广路径.
Dinic阻塞流算法	O(V2E)
MPM (Malhotra, Pramodh-Kumar and Maheshwari)算法	O(V3)	只适用于无环图。参考 .