文档介绍：网络流算法及其应用
  
网络流
网络流 network flows网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。
目录
定义
求最大流算法
最小费用最大流
有上下界的最大流
网络流算法
定义
图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，. 福特和 . 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D＝ （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短?��这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。
最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
假设 G(V,E) 是一个有限的有向图，它的每条边 (u,v)∈E都有一个非负值实数的容量c(u,v) 。如果(u,v)不属于E，我们假设c(u,v) = 0 。我们区别两个顶点：一个源点s 和一个汇点 t。一道网络流是一个对于所有结点 u 和 v 都有以下特性的实数函数 f:V×V→R
容量限制 (Capacity Constraints):
f(u,v)≤c(u,v)一条边的流不能超过它的容量。
斜对称 (Skew Symmetry):
f(u,v)=-f(v,u)由 u 到 v 的净流必须是由 v 到 u 的净流的相反（参考例子）。
流守恒 (Flow Conservation):
除非u = s或u = t，否则Σ（w∈V）f(u,w)=0 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。
注意 f(u,v) 是由 u 到 v 的净流。如果该图代表一个实质的网络，由 u 到 v 有 4 单位的实际流及由 v到 u 有 3 单位的实际流，那么 f(u,v) = 1 及 f(v,u) = − 1。
边的剩余容量 (Residual Capacity) 是 cf(u,v) = c(u,v)− f(u,v)。这定义了以 Gf(V,Ef)表示的剩余网络 (Residual Network)，它显示可用的容量的多少。留意就算在原网络中由u 到 v 没有边，在剩余网络乃可能有由 u 到 v 的边。因为相反方向的流抵消，减少由v 到 u 的流等于增加由 u 到 v 的流。扩张路径 (Augmenting Path) 是一条路径 (u1,u2...uk)，而u1 = s、uk = t及cf(ui,ui + 1) > 0，这表示沿这条路径传送更多流是可能的。
编辑本段求最大流算法
1、augment path，直译为“增广路”，其思想大致如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。
寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。