资源描述：
《最大流算法及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、最大流算法及其应用提要网络流相关的一些概念最大流和最小割问题最大流算法的应用总结一、网络流相关的一些概念流网络(FlowNetwork)流网络是一个有向图G=(V,E)，其中每条边(u,v)∈E均有一非负容量c(u,v)≥0。如果(u,v)∈E，则假定c(u,v)=0。流网络中有两个特别的顶点：源点s和汇点t。图1一个流网络的例子stv1v4v5v2v3v635221642314流(Flow)G的流是一个实值函数f，f(u,v)表示顶点u到顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：容量限制：对所有u,v∈V，要求f(u,v)≤c(u,v)。反
2、对称性：对所有u,v∈V，要求f(u,v)=-f(v,u)。流守恒性：对所有u,v∈V-{s,t}，要求流量整个流网络G的流量：割(Cut)流网络G=(V,E)的割(S,T)将划分成S和T=V-S两部分，使得s∈S，t∈T。定义割(S,T)的容量为c(S,T)，则：残留网络(ResidualNetwork)给定一个流网络G=(V,E)和流f，由f压得的G的残留网络Gf=(V,Ef)，定义cf(u,v)为残留网络Gf中边(u,v)的容量。如果弧(u,v)∈E或弧(v,u)∈E，则(u,v)∈Ef，且cf(u,v)=c(u,v)-f(u,v)。在下面的各种概念和方法
3、中，我们只考虑残留网络中容量大于0的弧，但是编程时为了方便还是保留了。增广路径(AugmentingPath)对于残留网络Gf中的一条s-t路径p称其为增广路径，定义增广路径p的残留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。增广(Augment)对于残留网络Gf中的一条增广路径p，增广的意思就是对于每一条属于p的弧(u,v)，将f(u,v)增加p的残留容量，将f(v,u)减少p的残留容量。这样的话，新的流f仍然满足流的三条性质，并且原流网络的流量
4、f
5、增加了。一般来说，增广过后就会修改残留网络，易得对于每一条属于p的弧(u,v)，要将cf(u
6、,v)减去p的残留容量，cf(v,u)加上p的残留容量。（程序实现基本都是通过直接修改残留网络来实现增广的）二、最大流和最小割问题最大流问题对于一个流网络G=(V,E)，其流量
7、f
8、的最大值称为最大流，最大流问题就是求一个流网络的最大流。增广路定理当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时，流f的流量
9、f
10、达到最大。（证明在此略去，可以参见相关书籍）根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G=(V,E)的流f置为零流，即对于(u,v)∈E时，f(u,v)=0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程
11、，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。Ford-Fulkerson方法的伪代码FORD-FULKERSON-METHORD(G,s,t)1initializeflowfto02whilethereexistsanaugmentingpathp3doaugmentflowfalongp4returnf最小割问题最小割是指流网络中容量最小的割。Ford-Fulkerson定理（最小割最大流定理）：在流网络中，最小割的容量等于最大流的流量。（证明也在此略去）根据这个定理，我们就可以通过求流网络的最大流
12、来得到最小割。最大流算法前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。这个方法的最大问题就在于怎样快速地找到一条增广路径。当然我们可以用最基本的搜索（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。本文将重点介绍一种高效且实用的最大流算法：SAP算法（最短增广路算法）。最短增广路算法即每次寻找包含弧的个数最少的增广路进行增广，可以证明，此算法最多只需要进行mn/2次增广。并且引入距离标号的概念，可以在O(n)的时间里找到一条最短增广路。最终的时间复杂度为O(n2m)，但在实践中，时间复杂度远远小于理论值（特别是加了优化之
13、后），因此还是很实用的。（此段中n表示顶点数
14、V
15、，m表示边数
16、E
17、）距离标号对于每个顶点i赋予一个非负整数值d(i)来描述i到t的“距离”远近，称它为距离标号，并且满足以下两个条件：d(t)=0对于残留网络Gf中的一条弧(i,j)，d(i)≤d(j)+1。允许弧和允许路如果残留网络Gf中的一条弧(i,j)满足d(i)=d(j)+1，我们称(i,j)是允许弧，由允许弧组成的一条s-t路径是允许路。显然，允许路是残留网络Gf中的一条最短增广路。当找不到允许路的时候，我们需要修改某些点的d(i)。算法基本架构ProcedureShortest_Augmenting_
18、Path;Var……Be
