最大流问题以及FF算法

最大流问题

问题描述：

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

约束条件：

设 G = (V, E) 是一个流网络，其容量函数为 c。设 s 为网络的源点，t 为汇点。G 的流的一个实值函数 f：V×V → R，且满足下列三个性质：

容量限制（Capacity Constraint）：对所有顶点对 u, v ∈ V，要求 f(u, v) ≤ c(u, v)。 反对称性（Skew Symmetry）：对所有顶点对 u, v ∈ V，要求 f(u, v) = - f(v, u)。 流守恒性（Flow Conservation）：对所有顶点对 u ∈ V - {s, t}，要求 Σv∈Vf(u, v) = 0。 f(u, v) 称为从顶点 u 到顶点 v 的流，流的值定义为：|f| =Σv∈Vf(s, v)，即从源点 s 出发的总流。

最大流问题（Maximum-flow problem）中，给出源点 s 和汇点 t 的流网络 G，希望找出从 s 到 t 的最大值流。

满足流网络的性质的实际上定义了问题的限制：

经过边的流不能超过边的容量； 除了源点 s 和汇点 t，对于其它所有顶点，流入量与流出量要相等。

示例结果：

上图最大流为 23，流向如下图所示

FF算法

Ford-Fulkerson 算法是一种解决最大流的方法，其依赖于三种重要思想： 残留网络（Residual networks） 增广路径（Augmenting paths） 割（Cut）

Edmonds-Karp算法 即最短路径增广算法 简称EK算法

EK算法基于一个基本的方法:Ford-Fulkerson方法 即增广路方法 简称FF方法

增广路方法是很多网络流算法的基础 一般都在残留网络中实现

其思路是每次找出一条从源到汇的能够增加流的路径 调整流值和残留网络 不断调整直到没有增广路为止

FF方法的基础是增广路定理(Augmenting Path Theorem):网络达到最大流当且仅当残留网络中没有增广路

EK算法就是不断的找最短路 找的方法就是每次找一条边数最少的增广 也就是最短路径增广.

Reference：

http://www.jianshu.com/p/1451e70909c8# http://www.cnblogs.com/gaochundong/p/ford_fulkerson_maximum_flow_algorithm.html http://www.cnblogs.com/Booble/archive/2011/03/04/1970453.html