?v[N];bool?used[N];
void?add_Node(int?from,int?to,int?cap)??//重边情况不影响
{
v[from].push_back((Node){to,cap,v[to].size()});
v[to].push_back((Node){from,0,v[from].size()-1});
}
int?dfs(int?s,int?t,int?f)
{
if(s==t)
return?f;
used[s]=true;
for(int?i=0;i<>
{
Node?&tmp?=?v[s][i];??//注意
if(used[tmp.to]==false?&&?tmp.cap>0)
{
int?d=dfs(tmp.to,t,min(f,tmp.cap));
if(d>0)
{
tmp.cap-=d;
v[tmp.to][tmp.rev].cap+=d;
return?d;
}
}
}
return?0;
}
int?max_flow(int?s,int?t)
{
int?flow=0;
for(;;){
memset(used,false,sizeof(used));
int?f=dfs(s,t,INF);
if(f==0)
return?flow;
flow+=f;
}
}
int?main()
{
int?n,m;
while(~scanf("%d%d",&n,&m))
{
memset(v,0,sizeof(v));
for(int?i=0;i<>
{
int?x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_Node(x,y,z);
}
printf("%d\n",max_flow(1,m));
}
}
关于网络最大流的两个算法
HEBEIUNIVERSITY
密级：
分类号：
学校代码：10075
学号：20100964
硕士学位论文
关于网络最大流的两个算法
学位申请人：毛晓亮
指导教师：毛华教授
学科专业：基础数学
学位类别：理学硕士
授予单位：河北大学
答辩日
期：二〇一三年五月
ClassifiedIndex:
U.D.C.:CODE:10075NO:20100964
ADissertationfortheDegreeofM.Science
TwoAlgorithmsabouttheMaxFlow
oftheNetwork
Candidate:MaoXiaoliang
Supervisor:Prof.MaoHua
Specialty:FundamentalMathematics
AcademicDegreeAppliedfor:MasterofScience
University:HebeiUniversity
DateofOralExamination:May,2013
摘要
摘要
网络最大流理论是图论研究中的一项重要内容，随着科技快速发展，尤其是计算机科学技术的日新月异，人们对于网络传输、交通路网设计、物资调动、图像处理等问题越来越关注，而网络最大流理论又是这些研究必不可少的基础，因此，网络最大流问题的进一步探索和讨论显得尤为重要和迫切。
目前，关于网络最大流理论的研究主要以增广路或割集两个方面为出发点，通过找出网络的所有增广路或者找出网络的最小割容量，进而得到网络的最大流。从实践上看，这种思想和方法是正确的和成功的。本文基于上述思想，对以增广路为出发点的Dinic增量网络算法进行分析和改进，同时进一步研究割集容量矩阵，得到解决网络最大流问题的两个算法，其主要内容如下：
第一，基于枢纽度的增广路算法。
以网络的连通性为切入点，引入枢纽度的概念，分析Dinic增量网络算法，通过构造实际运行的网络，指出Dinic增量网络算法在路径选择的顺序上存在的弊端以及由此产生的占路问题的严重性，说明此算法有待进一步提高。之后，在Dinic增量网络算法的基础上，通过修改增广路的选择顺序，得到基于枢纽度的增广路算法。
第二，二分部分割矩阵算法。
从网络的割集角度考虑最大流，对于出现的2n个矩阵方程，因其计算量过于庞大，常用的筛选算法使得最小割问题难于解决。针对此问题，本文提出部分割的概念，同时考虑原网络和对应的逆向网络，给出二分部分割矩阵算法，这样需要考虑的割集数量有效减少，从而计算量缩小，提高了最大流最小割定理的应用价值。此外，通过解决一个网络实例，说明此算法的有效性。
关键词网络最大流增广路枢纽度二分部分割逆向网络
Abstract
Abstract
Themaxflowofnetworkisanimportantpartinthestudyofgraphictheory.Withtherapiddevelopmentofscienceandtechnology,especiallycomputersciencetechnology,peopleputmuchmoreattentionondealingwiththeproblemssuchasnetworktransmission,transportation,resourcemobilizedandimage-processing.Thenetworkmaximumflowresearchisthefundamentalforalltheseproblems.Therefore,itbecomesmuchmoreimportantandurgentintheexploringandstudyingofthenetworkmaximumflowresearch.
Nowadays,theresearchonthenetworkmaximum-flowisbasedontwoaspects:oneisaugmentedpaths,andanotheriscutsets.Theysearchoutallofaugmentedpathsoralloftheminimumcutcapacitysoastoobtainthemaximum-flowinthenetwork.Thepracticalresultsshowthecorrectandsuccessofthisthoughtandapproach.Basedontheaboveideas,thispapergetstwoalgorithmsaboutthenetworkmaximum-flowbyanalyzingDinicalgorithmandthematrixofcutcapacity.Themaincontentsareasfollows.
First,thealgorithmofaugmentedpathbasedonpivotdegree.
Itstartsatconnectivityofthenetworkandgivesanewconceptcalledpivotdegree.Atthefollowing,itanalyzeswithDinicalgorithmandfindsoutitssomeshortagesinnetworkmax-flowproblemsuchastheorderaboutchosingaugmentedpaths.ThisanalysisexpressesthatDinicalgorithmneedstobecomemuchbetter.CombiningwithDinicalgorithm,itproposesanalgorithmofaugmentedpathbasedonpivotdegreeafterchangingtheorderoftheaugmentedpath.
Second,thealgorithmbasedonbinarypartialcut.
Westudyonthenetwork’scuts.Naturally,therearematrixequationswiththenumber2n.Thegeneralalgorithmscandifficultlyfindthemin-cutandsolvewiththeseequationsbecauseofitscharacteristicsofhugecalculations.Tosolvewiththeseproblem,weprovideaconceptofpartialcut.Consideringwiththeoriginalnetworkandtheinversenetwork,apartialcutalgorithmisgiven.Thealgorithmreducesthenumberofthecutsetandthequantityofcomputations.Asaresult,itimprovestheapplicationvaluesforthetheoremofmaximumflow-minimumcut.Inaddition,agivennetworkexampleshowstheeffectiveoftheprovidedalgorithm.
Keywordsnetworkmax-flowpivotdegree
binarypartialcutreversenetwork
目录
目
第1章
1.1
1.2
1.3
1.4
第2章
2.1
2.2绪录论.........................................................................................................................1研究背景........................................................................................................................1发展过程........................................................................................................................1主要研究内容................................................................................................................2本文文章结构................................................................................................................3网络流理论预备知识.................................................................................................4预备知识........................................................................................................................42F标号算法、Dinic算法和Greedy算法...................................................................8
2F标号算法...........................................................................................................9
Dinic算法...............................................................................................................9
Greedy算法..........................................................................................................102.2.12.2.22.2.3
第3章
3.1基于枢纽度的增广路算法.......................................................................................12基于Dinic算法的随机性分析...................................................................................12
实例分析...............................................................................................................12
原因分析...............................................................................................................153.1.13.1.2
3.2
3.3几个定义......................................................................................................................16基于枢纽度最大流算法..............................................................................................16
基于枢纽度最大流算法.......................................................................................17
算法可行性分析...................................................................................................17
算法正确性...........................................................................................................17
算法复杂性分析...................................................................................................18
网络实例...............................................................................................................18
算法进一步改进...................................................................................................20
网络最大流二分部分割矩阵算法...........................................................................24
割集算法讨论..............................................................................................................24
3.3.13.3.23.3.33.3.43.3.53.3.6第4章4.1
目录
4.2网络最大流二分部分割矩阵算法..............................................................................25
算法中的概念和相关定理证明...........................................................................25
二分部分割矩阵算法思想...................................................................................27
二分部分割矩阵算法...........................................................................................27
算法可行性分析...................................................................................................28
算法复杂性分析...................................................................................................28
网络实例...............................................................................................................28
总结与展望...............................................................................................................314.2.14.2.24.2.34.2.44.2.54.2.6第5章
参考文献...................................................................................................................................33
致谢.......................................................................................................................................35攻读硕士学位期间撰写的论文...............................................................................................36
第1章绪论
第1章绪论
本章将从网络流理论的发展历史出发，详细阐述网络最大流算法的发展历程，并结合部分算法实例，介绍其发展和研究现状，之后，给出本文的主要研究内容，最后给出本文的组织结构。
1.1研究背景
网络最大流理论的研究起源于Dantzig(1951)的网络单纯形法，随着Ford和Fulkerson（1956）标号算法[1,2]（也称2F算法）的提出，由图论出发的网络流理论才被系统的建立起来。50多年来，以2F标号算法为基础，大量新颖有效的算法陆续被提出，不断丰富和完善着网络流理论。近年来，随着计算机技术的迅猛发展，最大流算法复杂度的下界不断被改进，同时，理论算法的实现效率不断提高，进而使网络最大流理论在信息传输、路网交通、物资调运、配送、图像处理等领域的应用越来越广泛，应用价值也越来越高[3,4,5,6,7]。
尽管如此，网络最大流理论的研究还有以下主要问题有待解决：
(1)目前网络最大流算法时间复杂度的精确下界还没有被找到，更没有哪一种有效的算法，时间复杂度逼近最大流问题的下界。
(2)大量优秀算法被提出的同时，其实际实现问题也随之出现，许多算法的算法复杂度有所降低，但是实现起来却很困难，一般需要构建复杂的数据结构
它的实践中的应用。
(3)网络最大流理论在诸多领域都有很好的应用，随着理论研究的进一步深入，对于如何发现网络最大流理论的更多有价值的应用，本身就是一个值得研究的重要课题。[8,9,21,22]，限制了
1.2发展过程
下面用最大流理论发展过程中比较经典、颇具代表意义的几个算法为例，阐述其发展和研究现状。
河北大学理学硕士学位论文
第一，2F标号算法。1956年由Ford和Fulkerson提出的2F标号算法，又被称为增广路算法，即在剩余网络中不断寻找增广路，每找到一条增广路就进行一次增流，直至找到全部增广路为止。但是，对于复杂网络，增广路寻找本身就是一个极为棘手的问题，更为无奈的是，当网络的最大弧容量为无理数时，最大流序列不收敛[2]。除此之外，2F标号算法的时间复杂度依赖于网络中最大弧的容量值，因此，算法具有伪多项式性。
第二，Dinic增量网络算法。1970年到1973年，Dinic增量网络算法[23]的提出，使得最大流算法的复杂度进一步降低，由原来的O(vε2)和O(v2ε)降低到O(ε2logC)和O(vεlogC),其中C为整型网络的最大弧容量。此后很长一段时间，算法时间复杂度核心因子一直停留在O(vε)，没有能被突破。
第三，二分长度阻塞流算法。1998年，GoldBerg和Rao提出了二分长度阻塞流算法[32],进一步将算法时间复杂度降低，其复杂度为O(min{v2/3,ε1/2}εlog(v2/ε)logC)，此算法为现行算法中复杂度较低的，然而，算法本身极其复杂，实际实现起来比较困难。
在这些算法提出的同时，一些新的技术被提出和应用，使得最大流理论不断被充实和完善，比如：推进技术[11]、距离概念[21]、动态树[22]的建立等等，每种新技术都有其代表性的算法，尽管如此，每种算法仍然存在一定的弊端，未来在现有算法基础上的改进仍是一项很纷繁复杂的工作，同时也具有很大的挑战性。
1.3主要研究内容
本文通过对以往网络最大流经典算法的研究，分别从增广路和割集两个角度出发，以2F标号算法、Dinic算法、Greedy算法和割集矩阵算法为基础，通过算法实例，逐步改进Dinic算法、割集算法，给出基于枢纽度的增广路算法和基于逆向网络的二分部分割矩阵算法。
文中内容包含以下两部分：
第一部分，讨论以增广路为出发点的算法。
通过对Dinic增量网络算法进行系统的分析和研究，用具体网络实例，指出Dinic
第1章绪论
算法在增广路选择顺序上有待提高，由此造成增广路的占路问题将会导致无法得到网络的理论最大流。进而在此基础上通过网络顶点枢纽度的选择，逐步改进算法，最终给出基于枢纽度的增广路算法，同时给出具体的网络实例加以说明和验证本算法的可行性。
第二部分，讨论以割集为出发点的算法。
此部分内容主要讨论最大流最小割定理的实际性能问题，即以割集出发的网络最大流算法，针对一般矩阵方程计算量过于庞大和复杂的弊端，构建逆向网络和部分割，同时从原网络和对应的逆向网络中构造部分割，减少需要考虑的割集数量，在此基础上，通过集合的交和并运算，逐步简化割集容量矩阵，最终找出最小割集，即网络的最大流。
1.4本文文章结构
本文结构分以下五章进行组织：
第一章为绪论，主要介绍网络最大流理论的发展历程和研究现状，指出其中的一些研究方法和发展困难，并阐述本文的主要研究内容。
第二章为网络流理论的基本概念，详细地介绍了网络流理论中所涉及的一些基本概念和基本定理。
第三章为基于枢纽度的增广路算法，通过分析Dinic算法，结合2F标号算法和Greedy算法，逐步给出网络最大流基于枢纽度的增广路算法。
第四章为二分部分割矩阵算法，引入逆向网络和部分割，在网络中找出最小割，通过最大流最小割定理，得到网络的最大流。
第五章为总结与展望，首先对本文的主要内容和工作加以了综述，其次，阐述网络最大流理论算法的发展方向和发展趋势，以及本文给出的算法的进一步优化改进方向。
河北大学理学硕士学位论文
第2章网络流理论预备知识
本章给出本文所涉及的图论中网络最大流知识的相关概念及相关定理的阐述和证明，同时，介绍本文所要改进的网络最大流经典算法。
2.1预备知识
本节主要介绍图论及网络最大流理论的基本定义和性质[8,9,32]。
定义2.1.1对于由一个二元关系构成的集合，称之为图。具体来说，图是一个二元组(V,E)，其中非空集合V叫做顶点集，集合E是由V中元素构成的某些无序对的集合，称之为边集。图中顶点集V中的元素称为顶点，边集E中的元素称为边。图G的顶点数|V|称为图G的阶，边的数目|E|称为图G的边数。顶点所关联的边数（环边记两次）称为顶点的度，记为d(v).
定义2.1.2设G=（V,E），e=uv是G的一条边，若u与v重合，则e称为图G的环边；图G中连接u和v的两条或两条以上的边称为图G中u、v间的重边。
定义2.1.3图G中一个点边接续交替出现的序列ω=vi0ei1vi1ei2…eikvik称为图G的一条途径，其中vi0、vik分别称为途径的ω的起点和终点，ω上其余顶点称为中途点。
定义2.1.4图G中点和边都不重复出现的途径称为路。
注2.1.1若图G中u,v两点间有路相通，则称顶点u,v在图G中连通；若图中任意两点都连通，则称图G是连通图。
ur定义2.1.5每条边都规定了一个方向的图称为有向图。严格来说，一个有向图G是
urururur一个有序二元组(V(G),A(G))，其中V(G)是非空的顶点集，其元素称为顶点，集合A(G)
urA(G)（有序对，元素可重复），它是带有方向的边的集合，称为弧集，是V×V的一个子集
中的元素称为弧或有向边，指向某一顶点的弧称为该点的入弧，由该顶点发出的弧称为该顶点的出弧。
给它的每条边确定一个方向，便可得到一个有向图，注2.1.2①给定一个无向图G，
这个有向图称为G的一个定向图，而G称为这个有向图的基础图或底图。
②由无向图中顶点度的概念很自然的引申，有向图的顶点分为出度和入度两个概
urur+uur(v)；v的入念，对于图G，?v∈V(G)，v点的出度是指从v出发的弧的数目，记为dG
第2章网络流理论预备知识
?uur(v)。度是指指向v的弧的数目，记为dG
定义2.1.6一个网络N=（V，A）是指一个连通无环弧且满足下列条件的有向图：
(1)存在一个顶点子集X，其每个顶点的入度都为0;
(2)存在一个与X不相交的顶点子集Y，其每个顶点的出度都为0;
(3)每条弧都有一个非负的权值，称为弧容量。
注2.1.3①上述网络N可记为N=(V,X,Y,A,C)，其中X称为网络的发点集或源点集，Y称为网络的收点集或汇点集，网络中其他顶点称为中转点，C称为网络的容量函数，它是定义在弧集A上的非负函数。
②如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。由于，当对任意一个网络添加两个顶点s和t，分别作为人工源和人工汇后，此网络可导出一个单源单汇网络。因此，本文仅考虑单源单汇网络。
定义2.1.7N=(V,X,Y,A,C)的一个可行流是定义在A上的一个整值函数f，使得：
(1)对?a∈A,0≤f(a)≤c(a)(容量约束)；
(2)对?v∈V-(X∪Y),f-(v)=f+(v)(流量守恒)。
其中f-(v)表示点v处入弧上的流量之和，f+(v)表示点v处出弧上的流量之和。
注2.1.4①本文讨论的网络可行流主要是针对整数型流值，对于其他非整型流值的网络流，其定义与此类似。
②可行流一定存在，若?a∈A,f(a)=0，此时f(a)仍然是网络的一个可行流，这个流称为零流。
③对网络N中任一顶点子集S和任一可行流f，f+(S)表示从S中流出的流量，即从S中所有指向S外顶点的弧上的流量之和，f-(S)表示流入S的流量，即所有从S外的顶点指向S的弧上的流量之和。
④设f是网络N=(V,X,Y,A,C)中的一个可行流，则必有f+(X)=f-(Y)，f+(X)（或f-(Y)）称为此可行流f的流量，记为Valf，N中流量最大的可行流称为N的最大流。
定义2.1.8设N=(V,x,y,A,C)是一个单源单汇网络，S?V,S=V-S.(S,S)表示网络中尾在S中而头在S中的所有弧的集合（S中指向S之外的点的所有弧的集合），若x∈S,而y∈S,则称弧集K=(S,S)为网络N的一个割集或割，一个割集(S,S)的容量是指(S,S)中各条弧的容量之和，记为Cap(S,S)。
河北大学理学硕士学位论文
注2.1.5一个网络N有多个割，各个割的容量不一定相等，将所有割集中容量最小的割称为网络N的最小割。也就是说网络的一个割K称为最小割，当网络N中不存在这样的割K′使得CapK′<>
f是网络N中的一个可行流，对定义2.1.9设N=(V,x,y,A,C)是一个单源单汇网络，
N中的任一条弧a,
若f(a)=0，则称a是f零的；
若f(a)>0，则称a是f正的；
若f(a)=c(a)，则称a是f饱和的；
若f(a)<>
引理2.1.1对网络N中任一可行流f和任一割K=(S,S)，必有Valf≤CapK，其中等号成立当且仅当(S,S)中每条弧都是f饱和的而(S,S)中每条弧都是零的。
推论2.1.1设f是网络N中的一个可行流，K=(S,S)是N的一个割，若Valf=CapK，则f是网络N的最大流，而K是N的最小割。
定义2.1.10设u,v是网络N=(V,x,y,A,C)中任意两点，P是N的底图中一条连接u与v的路，若规定路P的方向为从u到v，则称这样规定了方向的路P为网络N中一条从u到v的路，简称为u-v路。同理，一条从源x到汇y的路称为一条x-y路。
注2.1.6设P=uv1…vkv是网络N=(V,x,y,A,C)中一条u-v路，若弧?vi+1,vi?∈A,则称此弧为u-v路P的一条反向弧（或称后向弧，逆向弧）；若弧?vi,vi+1?∈A,则称此弧为u-v路P的一条正向弧（或称前向弧，顺向弧），将u-v路P所经过的弧（无论正向弧或反向弧）称为路P上的弧。
定义2.1.11设f是网络N=(V,x,y,A,C)中的一个可行流，P是N中一条x-u路，u是N中任意一点，如果对路P上的任一条弧a，都有
(1)若弧a是P的正向弧，则c(a)-f(a)>0;
(2)若弧a是P的反向弧，则f(a)>0;
则称P是N中一条f可增x-u路。特别地简称N中一条f可增x-y路为N的一条增广路。
注2.1.7对N中任一条f可增路P和P上任一条弧a，令
?c(a)?f(a), a是P的正向弧，Δf(a)=??f(a), a是P的反向弧，
第2章网络流理论预备知识
则沿路P可增加的流量为Δf(P)=minΔf(a),该值称为f可增路P上流的增量或可增量，a∈P
增广路和可增量如图2.1.1和2.1.2所示，其中括号内的值表示弧容量，括号外的值表示
弧上现行的流。
图2.1.1
网络中的增广路，如粗线所示
图2.1.2网络沿增广路增流后的剩余网络
引理2.1.2（最大流最小割）任一个网络N=(V,x,y,A,C)中，最大流的流量等于最小割的容量。
注2.1.8①对于任一网络，若所有的弧容量都是整数，则最大流的流量也必为整数。②网络N=(V,x,y,A,C)中可行流f是N的最大流当且仅当N中不存在f可增路。定义2.1.12设网络N=(V,x,y,A,C)，Vi={v∈V|N中x到v的最短有向路长为i}，设x到y的最短有向路的长为n，则(1)x∈V0,y∈Vn;(2)ViIVj=?(j≠i)，Vi中的顶点成为
网络N的第i层顶点。
注2.1.9网络能否分层是网络本身的一种性质，针对这一性质有对应的分层算法[33]。定义2.1.13设网络N=(V,x,y,A,C)，f是N上的一个可行流，现构造一个新的网络N(f)=(V,x,y,A(f),C′)满足以下定义：
河北大学理学硕士学位论文
(1)当(u,v)∈A且f(u,v)<>
(2)当(u,v)∈A且f(u,v)>0，则(v,u)∈A(f)，且c′(u,v)=f(u,v)
称这样的网络N(f)为N的流值f的增量网络。
f为增量网络N(f)的一个可行流，引理2.1.3若f*为网络N=(V,x,y,A,C)的最大流，
则N(f)中的最大流流量为：Valf*-Valf。
注2.1.10当网络的可行流为零流时，原网络与增量网络显然相同。
如图所示：图2.1.4为图2.1.3
的增量网络：
图2.1.3网络N=(V,x,y,A,C
)
图2.1.4增量网络N(f)=(V,x,y,A(f),C′)
定义2.1.14N(f)为N的流值f的增量网络，N(f)按照最短有向路分层后，删去同层间的弧和由高层指向低层的弧，同时删去层数高于y的顶点，这样得到的网络称为原网络N的辅助网络，记为AN(f)。
2.22F标号算法、Dinic算法和Greedy算法
本节将介绍2F标号算法、Dinic算法和Greedy算法的内容（见文献[1,2,8,9,32]）。
第2章网络流理论预备知识
2.2.12F标号算法
Input：网络N=(V,x,y,A,C).
Output：网络N的最大流f.
Begin
Valf*=0;
whileN中存在增广路P
do
Δf(u,v)=minΔf(ui,vi),ui,vi∈P
Valf*+=Δf(u,v)；
更新网络；
End
注2.2.1从上面介绍的2F算法内容，可以看到，它还存在以下几点需要改进：①2F标号算法的复杂度不仅仅依赖网络的节点数和弧数，还依赖于弧上的最大容量。因此，标号算法不是多项式算法，而是伪多项式算法。
②当弧容量为无理数时，2F标号算法不能在有限步终止，并且最大流序列不收敛于最大流[2]，对于实际的网络中的弧容量，计算机处理的都是有理数，因此不会出现上述情况，但是就算法本身而言仍有待改进。
2.2.2Dinic算法
Input：网络N=(V,x,y,A,C).
Output：网络N的最大流f.
Begin
Valf*=0;
while(d(x,y)<>
do
begin构造N的分层网络
在增量网络N(f)中寻找增广路
删去饱和弧；
河北大学理学硕士学位论文
end
End
注2.2.2Dinic算法利用了最短增广路的思想，改进了2F标号算法，同时算法的复杂性也不再依赖于弧容量的值，已经成为多项式算法，克服了2F标号算法的伪多项式性，提高了网络最大流算法的有效性。
尽管如此，由于不是所有网络都可以分层[32]，因此对于一些复杂网络的最短增广路的选择Dinic算法仍有改进的可能，同时对于已经分层完毕的网络，Dinic算法寻找增广路的过程仍存在随机性，下一章将着重分析并解决此问题。
2.2.3Greedy算法
Greedy算法是求解最优化问题时常用的方法。它是在求解问题的过程中，总选择当前认为最优的情况，但是Greedy算法所得到的解仅仅是局部最优解，而不是整体最优解，对于一些局部最优则总体最优的问题，Greedy算法是一个有效的算法，但是对于非此类问题，Greedy算法往往得不到理论最优解[8]。
基于Greedy算法基础上的增广路算法
Input：网络N=(V,x,y,A,C).
Output：网络N的一个最大流Valf*
Begin
Valf*=0;S={x};
whileN中存在增广路
do
while(v!=y)
Δf(u,v)=maxΔf(u,vi),vi为u的邻点,u∈S；i∈N
S=SU{v};
令Δf(ui,vi)=min{Δf(u,v)|u,v∈S};
Valf*+=Δf(ui,vi)；
更新网络；
End
第2章网络流理论预备知识
注2.2.3Greedy算法的原则为每次把u的邻点中增量最大的点添加到增广路上，从而找到网络的最大流，事实上这种基于标号算法的过程往往依赖于弧容量，表现出很大的随机性。
河北大学理学硕士学位论文
第3章基于枢纽度的增广路算法
本章通过分析Dinic算法在实现过程中出现的问题，基于对此问题的分析和改进，提出基于枢纽度的增广路算法。
3.1基于Dinic算法的随机性分析
Dinic增量网络算法的基本思想是在寻找增广路之前先对网络进行分层，构造增量网络，进而在每层之间进行网络流推进，即寻找源点和汇点之间的最短增广路。但是在对增量网络进行操作时，如果增广路的标号选择顺序不同，有可能会出现两条增广路共用一条弧，而这条公共弧有可能沿一条增广路一次增流之后就已经被删去，致使实际增广路的数量达不到理论值，形成占路，最终导致无法找到网络最大流的理论值。因此，在增量网络中选择增广路的顺序有待进一步改进。
3.1.1实例分析
本节首先通过分析所构造的网络实例，用以说明占路问题。
例3.1.1.1如图所示网络N=(V,x,y,A,C)
，
图3.1.1N=(V,x,y,A,C)
图中弧上所示的数字为弧容量，为了寻找网络的最大流，不妨以零流作为可行流，运行Dinic算法。
以零流为初始可行流，则网络N=(V,x,y,A,C)的增量网络仍然是本身，由于本例中的网络已经是分层完毕之后的网络，因此，其辅助网络AN(f)也是原网络本身，只需在
第3章基于枢纽度的增广路算法
原网络中寻找增广路即可，任选其中的一条x-y路作为第一条增广路，不妨令P1=xuay，此路上的最小增量为2，则此时最大流Valf*=0+2=2，同时删去已被注满的弧，
更新网络：
图3.1.2
辅助网络中的增广路如粗线所示
图3.1.3增流完毕之后，删去已经饱和的弧
循环以上步骤，得到第二条增广路P2=xvcy，此时最大流变为：Valf*=2+2=4；重新
更新网络，得到：
图3.1.4第二条增广路如图中粗线所示
河北大学理学硕士学位论文
图3.1.5增流完毕之后删去已经饱和的弧
此时辅助网络AN(f)中已经不存在增广路，本次增流完成，重新构造原网络的增量
网络和辅助网络，继续寻找增广路，此时，网络的增量网络变为：
图3.1.6增流一次之后原网络的增量网络
辅助网络变为：
图3.1.7增流一次完毕后的辅助网络
显然，此时的网络已经没有增广路了，由注2.1.2(2)可知，当网络中不存在增广路时，网络达到最大流，因此，网络的最大流为Valf*=4.但是，网络的最大流理论值显然是Valf*=6，增广路的选择如图：
第3章基于枢纽度的增广路算法
图3.1.8原网络的理论最大流
于是，基于Dinic算法的增广路算法的随机性已显现出来，依据算法的过程，仅仅得到网络最大流的近似值，而没有达到理论最优解。
3.1.2原因分析
在2.2.2节中已经指出，Dinic增量网络算法的一些问题，上面通过一个具体网络实例说明占路问题存在。这类问题存在的主要原因是由于增广路选择的顺序不同，最终形成了占路问题，使得最大流实际值减少。进一步分析发现，在增广路选择过程中，Dinic增量网络算法破坏了增量网络原有的连通性质造成上述不确定性，具体原因分析如下：
(1)依照Dinic增量网络算法的思路，当一次增流完毕后就会删去已经饱和的弧，这样有可能在下一次寻找增广路的过程中破坏了网络原有的连通性，使得网络的可行流不能按照最优的路径进行增流。
(2)Dinic增量网络算法在选择增广路的过程中，并没有考虑此增广路上顶点顺序的影响，因此，改进的基础是依据顶点度的不同进行筛选。但是，当各个点的枢纽度一样的时候，仍然会出现上述问题，此时，增广路的选择又变成了无序的状态，致使占路问
题发生，如图所示：
图3.1.9网络中除源和汇之外，其余点的枢纽度相同
河北大学理学硕士学位论文
图中粗线所标示的是网络中现有的增广路，远远没有达到算法预期的结果，因此这中情况下，仍然需要进一步修改顶点选择的依据。
3.2几个定义
为表述简洁，本节将给出在即将介绍的算法过程中需要的一些概念。
定义3.2.1设网络N=(V,x,y,A,C)，任意u∈V，T?V，T={v|其中v为u的邻点}，
d(v)的倒数1/d(v)我们称v点的度（出度与入度之和）为了表示v点对于u点的重要程度，
为网络的枢纽度，记为Key(v)，将枢纽度最大的点称为枢纽点。
注3.2.1①枢纽度表示的是此点在网络连通性中的重要程度，换言之，删去此点对网络的连通性影响较大。
②枢纽度是一个相对的概念，考察的对象为与已知点相邻的点集中的点。
③对于一个给定的网络N=(V,x,y,A,C)，我们规定Key(x)=Key(y)=1，即，总是认为网络的发点和收点是枢纽点，其现实意义也是显而易见的。
定义3.2.2设网络N=(V,x,y,A,C)，对N中任一条f可增路P，若P上所有的点均为枢纽点，则称P为网络N的一条枢纽路。
注3.2.2枢纽路不一定是增量最大的增广路，选择枢纽路进行增流是为了保证网络中的枢纽点能优先被标号，使得增广路的选择具有顺序性。
例3.2.1如图1所示网络N=(V,x,y,A,C)
，
图3.2.1网络中的一条枢纽路
作为x的邻点，图中v1点的枢纽度大于v4点的枢纽度，因此选择v1为枢纽点。同理，图中粗线所标示的路为网络N=(V,x,y,A,C)的一条枢纽路。
3.3基于枢纽度最大流算法
针对3.1.2(1)分析的结果，本节通过枢纽路的寻找，在Dinic算法的基础之上，结合Greedy算法，给出一个基于枢纽度的网络最大流算法。
第3章基于枢纽度的增广路算法
3.3.1基于枢纽度最大流算法
Input：网络N=(V,x,y,A,C)(即初始可行流为零流的增量网络)
Output：网络N的一个最大流Valf*.
Begin
Valf*=0;S={x};
whileN中存在增广路P;
do
while(v!=y)
Key(v)=maxKey(vi),vi为u的邻点,u∈S;
S=SU{v};
令Δf(ui,vi)=min{Δf(u,v)|u,v∈S};
Valf*+=Δf(ui,vi);
c(uv)?=Δf(ui,vi),u,v∈S;
更新增量网络；
End
3.3.2算法可行性分析
本算法运行过程中，总是不断地在寻找枢纽点进行标号，当标到y时，形成一条增广路，按照最小增流值进行增流，之后更新网络，重新进行标号，继续寻找增广路，直至网络中不存在增广路为止。由2F标号算法可知，网络此时达到最大流。
本算法的核心思想是着重考虑网络的连通性，增加增广路选择的顺序性，从而减少标号算法盲目标号的弊端，避免Dinic增量网络算法出现的占路问题。
3.3.3算法正确性
下面的定理3.3.3将说明所给算法的理论上的正确性。
定理3.3.3基于枢纽度的增广路算法结束时，一定能得到网络最大流。
河北大学理学硕士学位论文
证明算法结束时，辅助网络中已不存在增广路，否则，必有得到标号的点vi，算法不会终止。于是，对应的增量网络中已无增广路，由注2.1.2(2)可知增量网络已经达到最大流，不妨设网络的最大流为f*，而增量网络N(f)的初始可行流f为零流，由引理
2.1.3可知，N(f)中的最大流为Valf*-Valf=Valf*-0=Valf*，即原网络已经达到最大流。
3.3.4算法复杂性分析
Dinic增量网络算法的复杂度为O(vε2)，由于基于枢纽度的增广路算法是在Dinic增量网络算法的基础之上进行的改进，因此，对网络分层和构造辅助网络的复杂性并没有变化，复杂性仅仅是在比较下一层的各个顶点的枢纽度上有变化，而对于这种比较，至多进行v-3次，于是整体的复杂度为O((v-3)vε2)=O(v2ε2)。
虽然基于枢纽度的增广路算法在计算复杂度有所增加，但是却克服了增广路的占路问题，能够精确地找到网络的最大流。
3.3.5网络实例
仍然以3.1.1节的网络为例，验证基于枢纽度的增广路算法的可行性。
例
3.3.5.1
图3.3.1验证基于枢纽度的增广路算法
首先，以零流为可行流，即Valf*=0，对源点x的邻点进行标号，考虑到Key(u)=1/3,Key(v)=1/2，Key(w)=1/3，因而选择v点作为枢纽路上的一点，v点的邻点仅有c点，因此，下一个枢纽点为c，同理，对y进行标号，于是第一条枢纽路形成，即P1=xvcy，Δf(P1)=2，因此，Valf*=0+2=2，第一次增流完毕，更新网络：
第3章基于枢纽度的增广路算法
图3.3.2验证基于枢纽度的增广路算法
图3.3.2中的粗线标示的即为已选择的枢纽路，网络更新后的弧容量分别为0,1,2.依据标号法的原则，此时c(xv)=f*(xv)，不再对v点进行标号，又由于Key(u)=Key(w)=1/3，故，任选一个点进行标号，不妨选择u点，则由Key(a)=1/3,Key(b)=1/2,故，标到b点，进而标到汇点y,得到第二条枢纽路P2=xuby，Δf(P2)=2，得最大流Valf*=2+2=4，
更新网络：
图3.3.3验证基于枢纽度的增广路算法
同理，寻找第三条枢纽路，这时同时对c点和a点进行标号，但c点已经标不到y，因此，选择a点，最终形成第三条枢纽路P3=xway，Δf(P3)=2，得到最大流为Valf*=4+2=6，
更新网络：
图3.3.4验证基于枢纽度的增广路算法
至此，网络中已经不存在枢纽路，即，找不到更多的增广路，因此，本次增流结束，继续考虑网络的增量网络和辅助网络：
河北大学理学硕士学位论文
图3.3.5
原网络的增量网络
图3.3.6原网络的辅助网络
此时，原网络的辅助网络中已经不能标号到汇点y了，因此网络已经达到最大流Valf*=6，这与3.1.1节中图3.1.8中的理论结果吻合，从而也证明了本算法的实际可行性。
本算法的网络实例是已经分层完成的网络，相对较简单，进一步讨论，针对所有可分层的网络而言，只要将网络分层，按照广度优先原则运行本算法，那么对于复杂网络的最大流问题，仍然是很好的解决方法。本算法的实际意义也很突出，比如雨季洪灾发生时，受灾群众的转移对于网络连通性的要求就是非常严格的，那么对于枢纽点的选择就是极其重要的。
3.3.6算法进一步改进
上节算法基于枢纽度考虑，优先考虑网络的连通性，在3.1.2(2)中构造了一个枢纽度完全一样的特殊网络，这对此种情形，上节算法仍然可以做进一步的改进。对于已经分好层的网络，如果每层的顶点的枢纽度相同，则任意选择其中一个顶点，之后，删去其中非枢纽路上的其他边，改变相关顶点的枢纽度，进而将问题转化为3.3.1中的情形。
Input：网络N=(V,x,y,A,C).
第3章基于枢纽度的增广路算法
Output:：网络N的一个最大流Valf*.
Begin
Valf*=0，S={x};
whileN中存在增广路P
do
while(v!=y)
Key(v)=maxKey(vi),vi为u的邻点，u∈S
if(u!=x)
delete非枢纽路上的边；
S=SU{v}；
令Δf(ui,vi)=min{Δf(u,v)|u,v∈S}；
Valf*+=Δf(ui,vi)；
c(uv)?=Δf(ui,vi),u,v∈S；
End
例3.3.6.1如图所示网络N=(V,x,y,A,C)：
利用改进的枢纽度增广路算法来求解3.1.2(2)
中网络的最大流。
图3.3.7N=(V,x,y,A,C)
初始化Valf*=0，S={x},考察x的邻点u，v，w，由于这三个点的枢纽度相同，因此，可以任意选择其中一个点作为枢纽路上的点，不妨选择u，得到：
河北大学理学硕士学位论文
图3.3.8选择u点作为枢纽点
此时网络中与u关联的点位a和b，而这两个点的枢纽度仍然相同，于是可以任意选择一个点作为枢纽点，不妨选择a，同时要删去与u和a关联的非枢纽路上的边ub，wa，
更新网络，得到：
图3.3.9修改已选点的枢纽度之后的网络
于是得到第一条增广路：P1=xuay
，沿这条增广路增流完毕之后，更新网络：
图3.3.10增流一次之后的网络
这样更新之后的剩余网络点的枢纽度已经不同，问题转化成了3.3.1的情形，于是剩
第3章基于枢纽度的增广路算法
余的两条增广路为P2=xwcy，P3=xvby，这样就找到了网络的所有增广路，也即找到了网
络的最大流：
图3.3.11剩余网络中的增广路
改进后的算法其复杂性没有增加，只是通过修改顶点的枢纽度来将问题转化为3.3.1节的情形，是上节算法的深入和完善。进一步地，对于分层网络的最大流推进，每两层之间与二部图的最大匹配时等价的，因此，等价的将已经匹配过的点删除并不会影响最大匹配数，也即不会影响最大流的流值，由此说明本改进算法是可行和正确的。
河北大学理学硕士学位论文
第4章网络最大流二分部分割矩阵算法
本章将着重从割集角度出发，利用最大流最小割定理，探寻网络最大流的优化算法。
4.1割集算法讨论
本节来讨论割集算法的理论，从割集的定义和最大流最小割定理可知，当已知网络达到最大流时，其最大流流值必然等于网络的最小割容量。对于一个给定的网络，其最大流必然存在，如何从复杂的网络中找到这个流值成为解决问题的关键。现已知网络的最大流流值等于网络的最小割容量，寻找到网络的最小割很自然地成为了问题的切入点。但是，寻找网络的最小割存在以下技术上的难题：
第一，要找到网络的最小割，须将网络的所有割集遍历，而对于复杂网络，尤其是弧的数量较大网络，每一个割集的构成本身就非常复杂，找到这样的割集有一定的困难。
第二，考虑一个极端情况，对于一个完全网络来说，即每两个点之间均连通的网络，割集数量非常庞大，为2n(n代表网络的顶点数量)个割集，从中找到最小割是一个非常困难的工作。因此，对于有效割集的筛选具有一定的难度。
第三，割集算法的理论依据主要是最大流最小割定理，从Ford和Fulkerson给出这个定理起，许多学者经过研究实验，也提出了很多优秀的基于割集的网络最大流算法，但是割集更多的是被应用于其他领域(可参见文献[26],[28],[30])，其应用于网络最大流的研究时，往往对网络具有很强的要求和限制，针对一般网络的算法还有一定的障碍。
由以上分析可知，要找到网络的最小割，必须遍历网络的所有割集，对于完全图而言，割集的数量将会达到2n个。从一个复杂网络中如何有序快速的构造筛选割集，是解决最小割寻找的关键。对2n个割集数据进行操作，这将是最大流最小割定理实际应用价值有待提高的一个主要障碍。对于现实存在的网络，依据其网络结构的性质，完全有可能将所需考虑的割集数量有效减少，从而使算法更加简便和有效。
第4章网络最大流二分部分割矩阵算法
4.2网络最大流二分部分割矩阵算法
4.2.1算法中的概念和相关定理证明
定义4.2.1(1)设网络N=(V,x,y,A,C)，任意v∈V,称点v的所有出弧构成的集合为网络N的一个部分割，记为Kv。
(2)下面的n-1阶容量矩阵T称为网络N的部分割容量矩阵
v1
v1?K11?v2?U
M?M?vn?2?U
vn?1??Uv2K12K22MKn?1,2LLLLvn?2K1,n?2K2.n?2Mvn?1K1,n?1?K2,n?1??M??Kn?2,n?1?Kn?1,n?1??Kn?2,2LKn?2,n?2LKn?1,n?2
其中Kij表示由顶点vi出发，且不指向vj的所有出弧的弧容量构成的集合，即，约
束的部分割；若vi与vj不连通，则Kij=U。
注4.2.1①由于Kij是由不同的弧容量构成的集合，每一个容量值的网络含义不同，表示指向不同点的出弧弧容量，因此，对于集合中相同的数值，我们以不同值处理。例如K={2,3,2,4}，其中的两个元素2视为不同元素。
②设T是网络N的一个部分割容量矩阵，取矩阵T的包含第一行K11的子集Q={K11,K1,j1,...,K1,jd?1}，以相同的方式取定列，构成原矩阵的d阶子阵Tjd。
?K11??Kj1Tjd=?1
M???Kjd?11K1,j1Kj12MKjd?12K1,jd?1??LKj1d?1?MM??LKjd?1jd?1??L
定义4.2.2设网络N=(V,x,y,A,C)，若将网络中所有弧的方向全部取反，则得到源与汇交换的一个新的网络，成为原来网络的逆向网络，记为N?1,由逆向网络产生的部分割矩阵成为原矩阵的逆矩阵，记为T?1。
定理4.2.1设网络N=(V,x,y,A,C),N?1=(V,y,x,A-1,C),则,N与N?1的最大流值相等。证明由于原网络与逆向网络的网络结构完全一样，仅方向不同，点集和弧集没有
河北大学理学硕士学位论文
发生变化，容量值也完全相同，则网络形成的增广路不变，每条增广路上的增流大小Δf(P)不变，因此，网络最终的最大流值不会发生变化。
定理4.2.2K=(S,S)是N=(V,x,y,A,C)的一个割集，若G(S)不连通，则K一定不是网络N的最小割。
证明若G(S)不连通，则G(S)必至少存在两个连通分支：G(S1)，G(S2)，此时割集K=(S,S)的容量为CapK=CapK1+CapK2，其中CapK1和CapK2分别是G(S1)和G(S2)形成的割集。显然，CapK<>
前面我们引入了部分割的概念，并构造了部分割容量矩阵，同时给出了此矩阵的子阵的取法，即：
?K11??Kj1Tjd=?1
M???Kjd?11
ddd
p=1q=1K1,j1Kj12MKjd?12K1,jd?1??LKj1d?1?MM??LKjd?1jd?1??L定理4.2.3若M(j)=UIKpq,j0=1,Kpq为Tjd中的元素，则Md(j)为网络的割集。
证明IKpq为vp点构成的不含内部弧的部分割，UIKpq为所选中的所有点构成的q=1p=1q=1ddd
部分割，即不存在内部弧的所有部分割，也就是网络的一个割集。
由定理4.2.2可知，对于K=(S,S)，只要选择网络中有连通关系的点构成S，依据上述矩阵的操作方法，就可以构造出网络的所有的割集，为了减少需要考虑的割集的数量，减少算法的复杂度，不妨将逆向网络的部分割矩阵引入进来，设网络N=(V,x,y,A,C)，N?1=(V,y,x,A-1,C),对于K=(S,S)，如果仅仅考虑S的话，|S|将会逐渐增大，最终将会达到|v|-1，这样割集的数量将会变大。但是，如果将原网络和逆向网络同时来考虑的话，割集数量将会减少，|S|仅需考虑得到(|v|-1)/2取整即可。现在证明这样一个事实：
定理4.2.4对于网络N=(V,x,y,A,C)，N?1=(V,y,x,A-1,C),若K=(S,S)，K-1=(S,S)，则CapK=CapK-1。
证明由逆向网络的定义，原割集中的弧必然和逆向网络中的弧弧容量相等，方向
第4章网络最大流二分部分割矩阵算法
相反，显然，没有其他的弧破坏原来的割集，故，CapK=CapK-1。
4.2.2二分部分割矩阵算法思想
本节二分部分割算法的思想如下：
首先，对于网络N=(V,x,y,A,C)，构造其逆向网络N?1=(V,y,x,A-1,C)，同时构造出两者的部分割矩阵；
其次，由连通性定理，寻找N的部分割矩阵的子阵，当子阵阶数较大时，转向求N?1的部分割矩阵的子阵；
最后，对子阵进行集合的并交运算，最终求得网络的最小割，也即，网络的最大流。
4.2.3二分部分割矩阵算法
Input：N=(V,x,y,A,C)，部分割矩阵T
Output：CapK*
Begin
K*=(S,S);CapK*=∞;
While(S中的点连通)
while(s=|S|<[(|v|?1)>
取定A，M=UIKpq;p=1q=1ssss
CapK*=min(CapK*,Plus(Ms));
while([(|V|?1)/2]<>
取定(A)，M=UIKpq;p=1q=1?1ssss
CapK*=min(CapK*,Plus(Ms));
OutputCapK*;
End
河北大学理学硕士学位论文
其中，对于任意的集合S={a1,a2,…an}，Plus(S)=∑a.i
i=1n
4.2.4算法可行性分析
由定理4.2.2可知，上述算法中构造的割集均为连通的点构成的，因此排除了孤立点构成的割集的干扰，同时不影响最小割的容量。由定理4.2.3，Md(j)为网络的一个割集，在原网络部分割矩阵和逆向网络的部分割矩阵中，包含了原网络的所有割集，于是，找出所有的Md(j)，取出最小值即为网络的最小割容量。
4.2.5算法复杂性分析
本算法提供了一种从割集角度考虑最大流的可行思路，由于要从已知网络中筛选出最小割，必然要遍历网络的所有割集，对于一个完全网络来说，割集数量为2n个，因此割集算法复杂度总体是不会降低的。但是，针对不同的网络，依据其不同的网络结构和性质，完全有可能将复杂网络转化成若干节点数较少的简单网络，基于此，网络最大流二分部分割矩阵算法的优势就将呈现，割集数量将不会超过2[n/2]?1，同时有效割集的组成元素，即S中的元素个数将不会超过[n/2]?1，于是，割集数量和割集结构都将会有效地得到简化，从而使得网络的最小割在此算法基础上能够被正确快速地找到。
4.2.6网络实例
例4.2.6.1如图所示网络N=(V,x,y,A,C)
：
图4.2.1弧上所标的数字为弧容量
首先，构造网络和逆向网络的部分割容量矩阵：
第4章网络最大流二分部分割矩阵算法
{8}{7}?UU?{7,8}?U?{4,3,1}{3,1}{4,1}{4,3}??T=??UU{8}UU?
?UU{6}{6,3}U?
??
?UUUU{5}??
??{8,6}{6}{8}UU?
U{4,3}{4}{3}U?
T?1=???UU{3,5}{5}{3}??
?UUU{7}U?
??
?UUU{8}{8,1}??
其次，依据算法要求，找出全体有效子阵：
1阶子阵：[{7,8}];
2阶子阵：??{7,8}{8}??
?U{4,3,1}??,?{7,8}{7}?
?U{5}??;
?{7,8}{8}U??{7,8}{8}U??{7,8}
3阶子阵：??U{4,3,1}{3,1}?,?U?,?U
??UU{8}???{4,3,1}{4,1}
????
?UU{6,3}????U
??{7,8}U{7}?
?U{6,3}U?
??;
?UU{5}??
对于4阶子阵取逆向矩阵的2阶子阵即可，即：
(A?1)2=??{8,6}{6}??12?{8,6}{8}?
?U{4,3}?，
?(A)=??U{3,5}?，
?
同理，5阶子阵就是逆向网络的1阶子阵：(A?1)1=[{8,6}];
再者，对各个子阵进行并交运算，得到：
M1={7,8};
M2={{8,4,3,1},{7,5}};
M3={{8,3,1,8},{8,4,1,6,3},{4,3,5},{7,6,3,5}};
{8}{7}?{4,3,1}{4,3}?,U{5}???
河北大学理学硕士学位论文
M4={{6,4,3},{8,3,5}};
M5={8,6};
最后，求出最小割：
CapK*=7+8=15,CapK*=8+4+3+1=16,CapK*=7+5=12,CapK*=8+3+1+8=20,CapK*=8+4+1+6+3=22,CapK*=4+3+5=12,CapK*=7+6+3+5=21,CapK*=6+4+3=13,CapK*=8+3+5=16,CapK*=8+6=14.
综上，minCapK*=min{15,16,12,20,22,12,21,13,16,14}=12.因此，网络的最小割容量为12，也即最大流为12。
至此，通过构建逆向网络和部分割矩阵，在连通性定理的基础上，可找到网络的最小割，即网络的最大流，算法实例也印证了二分部分割矩阵算法的可行性和正确性。
第5章总结与展望
第5章总结与展望
本文针对网络最大流问题提出两个算法：基于枢纽度的增广路算法和二分部分割网络算法。这两个算法是在经典算法的基础上进行的改进和创新，通过对Dinic增量网络算法的研究和分析，构造网络实例，找出算法改进的切入点，进而提出算法。
本文算法内容仍然以最大流研究的基本，即，网络的增广路和割集，对于增广路的选择，结合2F标号算法，Greedy算法，着重分析Dinic增量网络算法，给出了网络最大流的枢纽度算法，一方面克服了Dinic增量网络算法在增广路选择的无序性，同时，也使2F标号算法在增广路选择顺序方面得到了很好的改进，从而完整的找到了网络的理论最大流，使得算法的运行更加有效和更具目的性；而对于从割集方面，本文提出了部分割和逆向网络的概念，同时从原网络和逆向网络出发，对部分割容量矩阵进行集合间的并交运算操作，并最终得到有效割集，有效地减少了需要考虑的割集数量，使得基于割集的网络最大流算法过程更加简单，更加直观。
网络最大流算法研究迄今已有将近60年的历史了，多年来，众多学者通过不懈努力不断改进创新，提出了许多优秀的，切实可行的算法。但是，网络最大流算法的研究工作并没有停止，在现有算法的基础上仍然有许多工作和困难需要改进和创新，特别是以下几个问题。
第一，目前为止，网络最大流算法的时间复杂度的精确下界还没有被找到，也没有哪一种通用算法的时间复杂度趋于一个理论上的极小下界。因此，未来对于网络最大流的研究工作首要的是进一步降低其算法的时间复杂度，更进一步的，找到问题的下界，更加完善网络流理论。
第二，在网络流理论发展过程中，许多优秀算法被提出的同时，产生了一系列的新技术和新方法，对于这些新技术和新方法的进一步改进和应用，仍然是一项重要的并且切实可行的研究工作。
第三，通过本文的介绍知道，对于从割集出发的网络最大流算法的研究工作，面临着一个非常严峻的问题，即，割集数量的庞大性。对于一个复杂网络而言，很可能会出现2n个割集，而要从2n个割集中筛选出网络的最小割，是一个很困难的工作，目前的解决方法将会遇到很大的障碍。因此，如何应用一种新的技术或方法，解决这个问题，将
河北大学理学硕士学位论文
不仅仅是对于网络最大流问题的一种突破，很可能会对一系列其他问题带来突破口。
第四，现行网络最大流的很多优秀算法在理论上是复杂度较好的，但是实际的实现仍然存在很多的问题，如何在实际实现方面提供更多的技术支持也将会是网络最大流未来的研究趋势。
第五，网络最大流算法改进的同时，其实际应用价值也不断体现，现实生活中很多看似与网络最大流问题毫无关系的问题很可能将是最大流问题的一个演变，因此，如何在实际生活中发现最大流，利用最大流，将会极具现实意义。
综上所述，未来网络最大流理论的发展空间仍然很大，发展难度仍然存在，发展前景仍然十分良好，因此，更进一步的加深网络最大流的研究工作将会有很大的理论意义和实际价值。
参考文献
参考文献
[1]L.R.Ford,D.R.Fulkerson.Maximalflowthroughanetwork.CanadianJournalofMathematics.
1956,8:399-404.
[2]L.R.Ford,D.R.Fulkerson.FlowsinNetworksm.Princeton，PrincetonUniversityPress,1962.
[3]毛华,赵小娜,毛晓亮.危险品运输中的最小风险最大流.计算机工程,2012,38(9):268-270,
274.
[4]黄海,戚飞虎,岑峰.基于网络最大流的立体匹配算法.上海交通大学学报,2001,35(2):
168-172.
[5]谢民,高利新,管海娃.蚁群算法在网络最大流问题中的应用.计算机工程与应用,2008,44(22):
113-128.
[6]毛华,赵小娜,史田敏等.多部图的最大匹配算法.郑州大学学报(理学版),2013,45(1):27-29.
[7]周强峰,田铮,李小斌等.基于Gomory-Hu算法有效实现的图像区域分割.计算机应用,2008,
28(3):671-673.
[8]谢政.网络算法与复杂性分析理论.长沙,国防科技大学出版社,2003.
[9]J.A.Bondy.U.S.R.Murty.GraphTheory.Berlin,Springer,2008.
[10]党耀国,刘思峰,方志耕.网络最大流的割集矩阵算法．系统工程理论与实践,2003,9:125-128.
[11]张宪超,陈国良,万颖瑜.网络最大流问题研究进展.计算机研究与发展,2003,40(9):
1281-1292.
[12]邹豪思,王志远.网络最大流的矩阵算法.内蒙古大学学报,2001,32(2):456-469.
[13]R.K.Ahuja,J.B.Orlin,R.E.Tarjan.Improvetimeboundsforthemaximumflowproblem.SIAM
JournalonComputerScience,1989:118-123.
[14]L.R.Ford,D.R.Fulkerson.Asimplealgorithmforfindingmaximalnetworkflowsandan
applicationtotheHitchcockproblem.CanadianJournalofMathematics,1957,9:210-218.
[15]A.V.Goldberg.Recentdevelopmentsinmaximumflowalgorithms.TechnicalReport#98-045,NEC
ResearchInstitute,Inc,1998,4.
[16]M.Shigeno.Asurveyofcombinatorialmaximumflowalgorithmsonanetworkwithgains.Journal
oftheOperationalResearchSocietyofJapan,2004,47(4):244-264.
[17]R.K.Ahuja,T.L.Magnanti,J.B.Orlin.NetworkFlows:Theory,Algorithms,andApplications.New
jersey,PearsonEducationInc,1993.
[18]M.D.Grigoriadis.Anefficientimplementationofthenetworksimplexmethod.Mathematical
ProgrammingStudy,1986,26:83-110.
[19]厍向阳.点和边有容量约束的网络最小费用最大流算法.计算机应用研究,2010,27(8):
3112-3114,3119.
[20]毛华,毛晓亮,李斌.网络最大流部分割矩阵算法.计算机科学,2011,38(12):229-231,246.
河北大学理学硕士学位论文
[21]严蔚敏,吴伟民.数据结构(c语言版).北京,清华大学出版社.2009.
[22]F.M.Carrano.Datastructuresandabstructionswithjava.北京,清华大学出版社,2007.
[23]R.Aharoni,E.Berger,A.Georgakopoulos,etal.TheMax-FlowMin-Cuttheoremforcountable
networks.JournalofCombinatorialTheory,SeriesB,2011,101(1):1-17.[24]E.Boros,P.L.Hammer,R.Sun,etal.Amax-flowapproachtoimprovedlowerboundsforquadratic
unconstrainedbinaryoptimization.DiscreteOptimization,2008,5(2):501-529.
[25]E.A.Dinic.Algorithmforsolutionofaproblemofmaximumflowinnetworkswithpower
estimation.SovietMathematicsDoklady,1970,11:1277-1280.
[26]赵礼峰,白睿,宋常城.求解网络最大流问题的标号算法.计算机技术与发展,2011,12:
113-115.
[27]张宪超,江贺,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流.计算机学报,
2006,29(4):544-551.
[28]张宪超,陈国良.小容量网络上的最大流算法.计算机研究与发展,2011,38(2):194-198.
[29]张静,邱学绍.网络最大流模型算法及其实现.重庆大学学报(自然科学版)2006,29(5):132-134.
[30]吴艳,杨有龙,刘三阳.基于网络流矩阵求解网络最大流.系统工程,2007,25(10):122-125.
[31]A.V.Goldberg,S.Rao.BeyondtheFlowDecompositionBarrier.JournalofACM,1998,45(5):
783-797.
[32]高随祥.图论与网络流理论.北京,高等教育出版社,2009.
[33]X.YBai,D.Marcotte,R.Simon.Undergroundstopeoptimizationwithnetworkflowmethod.
Computers&Geosciences,2013,52(3):361-371.
[34]F.J.Brandenburg,M.CCai.Shortestpathandmaximumflowproblemsinnetworkswithadditive
lossesandgains.TheoreticalComputerScience,2011,412(4-5):391-401.
[35]A.Elalouf,R.Adany,A.Ceder.FlowExpansiononTransportationNetworkswithBudget
Constraints.Procedia-SocialandBehavioralSciences,2012,54(4):1168-1175.
[36]A.Shioura.TheMA-orderingmax-flowalgorithmisnotstronglypolynomialfordirectednetworks.
OperationsResearchLetters,2004,32(1):31-35.
致谢
致谢
本论文是在导师毛华教授的悉心指导下完成的。从论文的选题、实验方案的设计、结果分析到论文的撰写，都倾注了毛老师的大量心血和辛勤汗水。毛老师深厚的理论功底、丰富的实践经验、严谨求实的治学态度，让我受益匪浅。此外，在生活上毛老师也给予我很大的关怀。毛老师在论文撰写过程中为我解决了很多疑难问题，她循循善诱的教导和不拘一格的思路都给予我很大的帮助。
感谢我所有的同学和朋友，在我研究生学习、实验和生活中给予的帮助和支持。在此还要特别感谢我的师妹。在我的论文遇到技术难题时，她给予我莫大的帮助。
在此文完成之际，谨向两年来给予我关心的良师益友和亲人们致以最诚挚的谢意!同时向对论文进行评审并提出宝贵意见的各位专家和导师表示深深的谢意！
河北大学理学硕士学位论文
攻读硕士学位期间撰写的论文
[1]毛华,毛晓亮,李斌.网络最大流部分割矩阵算法.计算机科学,2011,38(12):
229-233.
[2]毛华,赵小娜,毛晓亮.危险品运输中的最小风险最大流算法.计算机工程,2012,
38(9);268-270.
[3]毛华，赵小娜，史田敏，毛晓亮等.多部图的最大匹配算法.郑州大学学报(理学版),
2013,45(1):27-29.
几种网络最大流算法比较
学号：
本科毕业论文
学 院 计算机与信息技术学院 专 业 计算机科学与技术专业 年 级 2010级 姓 名 闫佳晖
论文题目 几种网络最大流算法比较 指导教师 冯岩 职称 副教授
2014年 4 月 28 日
目 录
摘 要 ................................................................... 1
Abstract ................................................................... 1
1 绪论 ................................................................... 2
1.1最大流问题的研究背景及发展情况 ..................................... 2
1.2选题意义 ........................................................... 2
2 预备知识 ............................................................... 3
2.1 图论 .............................................................. 3
2.2 网络最大流算法 .................................................... 4
3 几种网络最大流算法的分析与比较 ......................................... 4
3.1 Ford-Fulkerson算法 .................................................. 5
3.1.1算法介绍与分析 ............................................... 5
3.1.2算法实现 ..................................................... 5
3.2 Edmonds-Karp修正算法 .............................................. 7
3.2.1算法介绍与分析 ............................................... 7
3.2.2算法实现 ..................................................... 8
3.3 dinic算法 ......................................................... 11
3.3.1算法介绍与分析 .............................................. 11
3.3.2算法实现 .................................................... 13
3.4 算法比较 ......................................................... 15
4 结论 .................................................................. 16
参考文献 ................................................................ 17
几种网络最大流算法比较
学生姓名：闫佳晖 学号：20105101106
计算机科学与技术学院 计算机信息与技术专业
指导教师：冯岩 职称：副教授
摘 要：本文主要研究的是网络最大流问题。论文从算法的思想、复杂度、应用范围及实际运行效率研究3种传统算法（Ford-Fulkerson算法，Edmonds-Karp修正算法，Dinic算法）。Ford-Fulkerson是一种迭代方法，采用的是深度优先策略。它的实际运行效率取决于如何确定增广路径，应用在工业和农业等领域。Edmonds-Karp修正算法用宽度优先取代了深度优先，应用在工程和商业等领域。Dinic算法是将顶点按照其与发点的最短距离分层。分层时用宽度优先法，而寻求增广路径时则采用深度优先策略。Dinic算法应用在工业、工程和运输业等领域。
关键词： 图；算法；标号；网络流；最大流
Abstract：This paper mainly studies the network maximum flow problem. We compare three traditional algorithms (Ford - Fulkerson algorithm, Edmonds - Karp correction algorithm, Dinic algorithm) from thought, complexity, application range and study on the efficiency of the actual operation. Ford - Fulkerson is a iterative method and uses the depth first strategy. Its efficiency of the actual operation depends on how to determine the augmenting path, and it is used in industrial and agricultural areas. Edmonds-Karp correction algorithm uses breadth first to replace the depth first, and it is applicated in engineering and business areas . Dinic algorithm layers the shortest distance between the vertices according to stratification and the starting point. We use the breadth first method while layering.But when seeking the augmenting paths,we use the depth first strategy.The application of Dinic algorithm is in the industrial, construction and transportation industries etc.
Keywords：Graph；Algorithm;Labeling；Network flow；Maximum flow；
1.绪论
1.1最大流问题的研究背景及发展情况
最大流问题属于网络分析问题，它是指在一定条件下，要求所流过网络的物流、信息流、能量流等流量为最大的问题。比如交通运输网络中的车流、物流、供水网络中的水流、通信系统中的信息流等等，都属于网络最大流问题[1]。
在研究最大流问题的过程中，人们建立了比较完善的最大流问题的理论，与此同时也开发了许多算法，如Ford-Fulkerson算法，最大容量增广路算法，Dinic算法等等，这些经典的算法以及相关的技术对于网络最大流研究起到了至关重要的推动作用。近些年来，随着网络和计算机科学技术的飞速发展，网络最大流问题得到更加深入的研究，并且极大推动了网络最大流问题的研究进程[2,3]。
最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 [4]。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
最早研究网络最大流问题的是美国学者希奇柯克（Hitchcock），他在1941年的时候研究铁路运输和生产组织方面的线性规划问题时提出了运输问题的基本模型；然而后来柯普曼（Koopmans）在1947年的时候独立的提出了运输问题并且对此问题详细地加以讨论[5]；从19世纪40年代开始，康脱洛维奇（Kantorovich）也围绕运输问题做出了大量的研究，这与一般的线性规划问题不一样，它的约束方程组中的系数矩阵有特殊的结构。
一些外国的学者从算法角度上考虑，对于网络最大流问题的解决提出了许多可行的办法，例如图上求解法以及运用计算机来实现的启发式多种算法等。国内对网络最大流的研究主要非为3个方向：一是基于国外算法的基础之上，对网络最大流问题的算法进行改进研究；二是从目标函数出发，在网络最大流问题中有些时候需要考虑成本如何最小、运输过程中货物的损坏率怎样才能最低以及单位运价的变化调整等许多
目标；三是从约束函数的角度出发，研究需求量和供给量在区间变动的不确定型的运输问题、时间窗口运输问题等。
1.2选题意义
网络流问题主要研究的是网络最优化问题,在工程及科学等领域均有重要作用。其主要内容包括最短路、最大流及最小费用流等问题,随着信息技术的发展人们建立了较为完善的理论,提出了一系列相应的算法,取得了令人瞩目的成绩。
而且我们在日常生活中时常遇到这样一些图，如旅游线路图、交通图、管道系统图等。这些图在优化理论中就是所谓的对所对应的实际情况进行的抽象和概括，用图来表示我们研究的对象以及对象之间的联系是很方便、直观的。比如网络通信、旅游管理、金融系统、交通运输等问题都可以用网络图来表示。
最大流问题应用极其广泛，很多生活中的问题都可以转化为最大流问题，其难点是从实际生活中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。
2.预备知识
2.1图论
所谓的图论，顾名思义就是研究图的理论。图论中的图是由一些实际问题经过抽象而得到的，由点和点与点之间的线构成，它能反映一些对象之间的关系。图形中的点表示一些对象(如通讯站、选手、工序等)，两点之间的有向或者无向的线表示对象之间有某种特定的关系(如胜负关系、先后关系、连接关系、传递关系等)[6]。
电路网络、物质结构、交通运输、城市规划、物资调配、信息传递等都可以用点和线连接的图进行模拟。而这里研究的图和平面几何中的图有些不一样，这里只关心图中有几个点，点与点之间有没有线，至于连线的方式是曲线还是直线点与点的相对位置怎样都是无关紧要的[7]。
下面介绍一些网络最大流问题会用到的相关的定义：
定义1：由点和边构成的图为无向图，记为G=(V,E)；由点和弧构成的图为有向图，记为D=(V,A).
定义2：在无向图G中，若存在一个点边交错序列(vi1,ei1,vi2,ei2,?vik-1,eik-1,vik)，满足
eit=[vit,vit+1](t=1,2,?k-1)，则称之为一条联结vi1和vik的链，记为(vi1,vi2,?,vik),若vi1=vik，则称之为圈。
定义3：在有向图D中，若存在一个点弧交错序列(vi1,ai1,vi2,ai2,?vik-1,aik-1)，弧ait的始点为vit，终点为vit+1，记为ait=(vit,vit+1)，则称这条点弧的交错序列为从vi1到vik的一条路，记为(vi1,vi2,?,vik)。若路的第一点和最后一点相同，则称之为回路。
链与路中的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。 定义4：如果对于一个有向图D的每一条弧，相应有一个权数cij，称这样的图为网络,记为D=(V,A,C) [6] 。
一般在网络图中，每条弧的权代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络。
2.2网络最大流算法
要想知道什么是网络最大流算法就必须先要知道什么是网络最大流问题，那什么是网络最大流问题呢？所谓网络最大流问题就是，给了一个带收发点的容量网络N，求N上使达到最大的可行流(称这样的可行流为最大流)。 我们先将一个复杂的网络问题进行转化，使之成为典型的网络问题，再对相应的限制条件进行抽象化、理论化，在此基础上，进行分析和研究，找出解决办法。最大流问题已经有40多年的研究历史，这短时间内，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如Ford-Fulkerson算法，Edmonds-Karp修正算法，Dinic算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的研究。
所谓的网络最大流问题就是在一个有向连通的图中，指定一个点为发点，另外一个为收点，其他的都称为中间点，在所有的点都能够承受的情况下，通过这个网络图的最大的可行流，即为发点到收点的最大的可行流。[8]。
众所周知，在1955年 ，T.E.哈里斯在研究铁路的最大通量时提出在一个给定的网络上来寻求两点间最大运输量的问题。而在1956年，L.R. 福特和 D.R. 富尔克森等人就给出了这类问题的解决算法，从而建立了网络流理论。所谓网络或者容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是顶点集，E是有向边集，C是弧上的容量。除此外顶点集中还包括一个起点和一个终点。网络上的流就是从起点流向终点的可行流，这就是定义在网络上的非负函数。但是它一方面要受到容量的限制；而另一方面，除去起点和终点之外，所有中途点都要求保持流入量和流出量的平衡。如果把一个图看作公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。如果把一个图看作输油管道网 ， v1 表示发送点，v6表示接
收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。
3.几种网络最大流算法的分析与比较
本文所研究的几种算法在众多求解网络最大流算法中是比较常用的，也是网络最大流算法中比较典型的例子，能够代表相当一部分的网络最大流算法。下面就来分析一下具体的算法。
3.1 Ford-Fulkerson算法
3.1.1算法介绍与分析
Ford-Fulkerson算法是一个找最大流f的算法。它是由Fulkerson和Ford在1957年最早提出的[9]，基本思想是从任意一个可行流出发，寻找—条增广路径，并且在这条增广路径上增加流量，于是便得到一个新的可行流，然后再在这新的可行流上找一条新的增广路径，然后再增加流量……，接着继续这个过程，一直到找不到新的增广路径为止。
用Ford-Fulkerson求最大流问题的时候，一个点只有以下三种状态：1、标号已检查；2、标号未检查；3、未标号。
Ford-Fulkerson算法总共分为两个过程：一是标号过程：通过标号找到一条增广路径；二是增广过程：沿着增广路径来增加网络流的流量[10]。下面我们来分析一下Ford-Fulkerson算法的复杂度，时间复杂度为O(m*n*u)。其中m为弧的数目，n是迭代次数，u为弧上容量最大上界，是伪多项式的算法。邻接表来表示图，空间复杂度为O(m+n)。而Ford-Fulkerson方法的实际运行效率也取决于如何确定增广路径。如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同。
Ford-Fulkerson是一种迭代方法，它采用的是深度优先策略。
3.1.2算法实现
下面我们来将Ford-Fulkerson算法具体实现一下:
#include #include using namespace std;
const int maxN=201;
static int edge[maxN][maxN];
bool visited[maxN];
int father[maxN];
int N, M;
int ans;
void Ford_Fulkerson( )
{ while(1)
{
queue q;memset(visited, 0, sizeof(visited)); memset(father, -1, sizeof(father));
int now; visited[0] = true; q.push(0);
while(!q.empty())
{ now = q.front(); q.pop();
if(now == M-1) break;
for(int i=0; i
{
if(edge[now][i] && !visited[i])
{ father[i] = now; visited[i] = true; q.push(i); }
}
}
if(!visited[M-1]) break;
int u, min = 0xFFFF;
for(u=M-1; u; u=father[u])
{ if(edge[father[u]][u] < min)="" min="edge[father[u]][u];">
for(u=M-1; u; u=father[u])
{ edge[father[u]][u] -= min; edge[u][father[u]] += min;
}
ans+=min;
}
}
int main()
{ int s, e, w;
while(cin >> N >> M)
{ ans=0;
memset(edge, 0, sizeof(edge));
for(int i=0; i
{ cin>>s>>e>>w; edge[s-1][e-1]+=w; }
Ford_Fulkerson();
cout < ans=""><>
}
return 0;
}
3.2 Edmonds-Karp修正算法
3.2.1算法介绍与分析
最大流算法Edmonds-Karp简介：若给定一个可行流F=(Fij)，我们把网络中使
Fij=Cij的弧称为饱和弧，Fij<>
我们添加一条从i到j且容量Cij=0的弧，这样整个流网络变成一个完全图。如果从
i到j有流量Fij，则从j到i的流量定义为Fji = -Fij 。考虑一条从源点s出发到汇
点t的路径p，如果对于每一段弧(i,j)属于p都有Fij <>
是未饱和弧，则我们可以向这条路径上压入更多的流，使得其中的一条弧达到饱和。这样的路径p叫做可改进路，可压入的流量叫做该可改进路的可改进流量。重复这个过程，直到整个网络找不到一条可改进路，显然这时候网络的流量达到最大。Edmonds-Karp算法就是利用宽度优先不断地找一条从s到t的可改进路，然后改进流量，一直到找不到可改进路为止[2,3,11]。
对于Ford-Fulkerson来说,由于增广路径选取的任意性使该Ford-Fulkerson算
法不是一个好的算法，所以Karp和Edmonds对Ford-Fulkerson算法作出了修正，总的来说也就是一句话：先给标号的先扫描。意思是对已经给标号的顶点v进行扫描时，先对所有和v邻接的未给标号的顶点给予标号。所以Edmonds-Karp算法的修正实质是对顶点给标记的过程采用了宽度优先的策略，从而使得流量增加总是沿着长度最短的那条路径从s流向t的。
这个模版的代码完全按照BFS从源点逐个遍历增广路径,得到最大增广容量,通过不断调整,最后求得最大流量,值得注意的是,最后一次BFS后所标的路线即为最小截集,即所谓的瓶颈,据此很容易求出最小截集的容量。由于用宽度优先，每次找到的可改进路是最短的可改进路，通过分析可以知道其时间复杂度为O(m2n), 该算法的运行时间是伪多项式的，但不是真正多项式的。邻接表表示图，空间复杂度为（n+m）。
Edmonds-Karp修正算法的实质也是一种分层，如果说Ford-Fulkerson算法是采用了深度优先策略。Edmonds-Karp修正算法则是用宽度优先取代了深度优先。
3.2.2算法实现
#include #include #include #include #include
#include #define Maxn 100
#define Maxnum 99999999
using namespace std;
int n, f[Maxn][Maxn], g[Maxn][Maxn], s, t;
int path[Maxn], pre[Maxn], pathlen;
bool vis[Maxn];
void init()
{
scanf("%d", &n);
scanf("%d%d", &s, &t);
for (int i=0; i
scanf("%d", &g[i][j]); }
void get_path(int a, int b) {
if (a == b) path[pathlen] = a; else
if (pre[b] != -1) {
path[pathlen++] = b; get_path(a, pre[b]); } return; }
int Edmonds_karp() {
int maxf = 0, minc; bool flag;
memset(f, 0, sizeof(f));
while (true) {
queue q; q.push(s);memset(path, 0, sizeof(path)); memset(pre, -1, sizeof(pre)); memset(vis, false, sizeof(vis)); vis[s] = true; flag = false; while (!q.empty())
int now = q.front(); q.pop();
for (int j=0; j
if (g[now][j] != f[now][j] && !vis[j]) {
q.push(j);
vis[j] = true; pre[j] = now; if (j == t) {
flag = true; break; } }
if (flag) break; } if (flag) {
pathlen = 0; minc = Maxnum;
get_path(s, t); for (int i = pathlen; i > 0; i--)
minc = g[path[i]][path[i-1]] - f[path[i]][path[i-1]]; for (int j = pathlen; j > 0; j--) {
f[path[j]][path[j-1]] += minc;
f[path[j-1]][path[j]] = -f[path[j]][path[j-1]]; } } else
for (int i = 0; i < n;="" i++)="" maxf="" +="f[s][i];" break;="" }="">
return maxf; }
int main() {
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); init();
int ans = Edmonds_karp(); printf("%d\n", ans); return 0; } 3.3 Dinic算法 3.3.1算法介绍与分析
Dinic算法是从带发点Vs和收点Vt的容量网络S的任一可行流f0 (例如零流)开始，构造S的关于f0的分层增量网络AS(f0)，在AS(f0)中找一条从Vs到Vt的增广路
1f0径u，对f沿u进行增广得到可行流，在AS(f)中删去u上容量最小的弧，并相
11
ff00应修改AS(f0)上弧的容量，得到网络AS()，然后可以在AS()中再找一条从Vs
12ff00到V的增广路径u，对沿u进行增广得到可行流，重复上述步骤依次得到S的
t
可行流
f01,f02,,f0p=f1
，因为AS(f0)只有有限条弧，每次至少删一条，所以有限步
后必然会使剩下的网络不再存在增广路径，Vt在AS(f1)中的层数一定大于它在AS(f0)中的层数；针对AS(f1)重复上面的做法，在有限次增广后一定会得到S的可行流f2，使Vt在AS(f2)中的层数更大。由于Vt的层数最多为n-1（n是网络S的顶点数）。所以经过有限步后得到S的可行流fk，S中不再有fk的增广链，这时fk就是S的最大流
[2,12,13]
。
Dinic算法的具体步骤如下： 1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束 3、在层次图内用一次dfs过程增广 4、转步骤2 下面是dfs的过程： p←s;
While outdegree(s)>0 u←p.top; if u<>t
if outdegree(u)>0
设(u,v)为层次图中的一条边; p←p,v; else
从p和层次图中删除点u, 以及和u连接的所有边; else
增广p（删除了p中的饱和边）; 令p.top为p中从s可到达的最后顶点; end while
在程序里，p表示找到的增广路径，p.top为路径中的最后一个定点。一开始，P中只有源点。
整个While循环分为2个操作。如果p的最后一个顶点为汇点，也就是说找到了增广路，那么对p增广，注意到增广后一定有一条或多条p中的边被删除了。这时，我们使增广路径后退至p中从源点可到达的最后一个顶点。如果p的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u连出的一条边，比如(u,v)，我们就将顶点v放入路径p中，继续dfs遍历；否则，点u对之后的dfs遍历就没有用了，我们将点u以及层次图中连到u的所有边删除，并且在p中后退一个点。Dfs过程将会不断重复这2个操作，直到从源点连出的边全部被删除为止[14]。
由于在Dinic算法的执行中，每次都要重新分层，汇点所在的层次也是严格递增的，而且n个点的层次图最多有n层，所以Dinic算法最多重新分层n次。在层次图中，因为每条增广路径都有瓶颈，而且两次增广的瓶颈都不可能一样，所以增广路径最多有m条。搜索每一条增广路径时，回溯和前进都最多有n次，因此时间复杂度是O(nm)；而沿着同一条路径(i,j)不可能枚举两次，因为第一次枚举的时候要么这条边的容量已经用尽，要么j到汇点不存在通路从而使其从这一层次图中被删除[15]。综上所述Dinic算法时间复杂度理论的上界是O(n2*m)，其中m为弧的数目，n是迭代次数，是多项式算法。邻接表表示图，空间复杂度为（n+m）。
Dinic算法是将顶点按照其与发点的最短距离分层，分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略。 3.3.2算法实现
下面是dinic的代码实现： #include #include #include #include using namespace std; const int N=20;const int INF=0x3f3f3f3f; int s[N][N]; int d[N]; int n,m;
int min(int a,int b) {
return a
bool bfs() {
queueQ;memset(d,-1,sizeof(d));
d[1]=0; Q.push(1); while(!Q.empty()){
int v=Q.front();Q.pop(); for(int i=1;i<=n;i++){ if(d[i]="=-1&&s[v][i]){" d[i]="d[v]+1;" q.push(i);="" }="" }="">
return d[n]!=-1; }
int dfs(int v,int cur_flow) {
int dt=cur_flow; if(v==n)return cur_flow; for(int i=1;i<>
if(s[v][i]>0&&d[v]+1==d[i]){ int flow=dfs(i,min(dt,s[v][i])); s[v][i]-=flow; s[i][v]+=flow; dt-=flow; } }
return cur_flow-dt; }
int dinic() {
int cur_flow,ans=0;
while(bfs()){
while(cur_flow=dfs(1,INF)) ans+=cur_flow; }
return ans; }
int main() {
int t,i,cas=0,u,v,w; scanf("%d",&t); while(t--){
memset(s,0,sizeof(s)); scanf("%d %d",&n,&m); for(i=1;i<>
scanf("%d %d %d",&u,&v,&w); if(u==v)continue; s[u][v]+=w; }
printf("Case %d: %d\n",++cas,dinic()); }
return 0; }
3.4 算法比较
本文介绍了Ford-Fulkerson算法、Edmonds-Karp修正算法以及Dinic算法，这3个算法都是网络最大流算法中较为经典的算法，各自都有各自的特点，下面就将它们的特点比较一下。
Ford-Fulkerson算法的是采用深度优先策略，是网络最大流的基础算法；Edmonds-Karp算法是对顶点给标记的过程采用了宽度优先的策略，用宽度优先取代了深度优先，从而使得流量增加总是沿着长度最短的那条路径从s流向t的；Dinic算法是将顶点按照其与发点的最短距离分层，它兼取了Ford-Fulkerson算法和
Edmonds-Karp修正算法的优点，在分层时用宽度优先法，寻求增广路径时用深度优先策略。
Ford-Fulkerson算法时间复杂度为O(m*n*u)，其中m为弧的数目，n是迭代次数，u为弧上容量最大上界，是伪多项式的算法。邻接表来表示图，空间复杂度为O(m+n)；Edmonds-Karp算法由于用宽度优先，每次找到的可改进路是最短的可改进路，通过分析可以知道其时间复杂度为O(m2n)，其中m为弧的数目，n是迭代次数。邻接表表示图，空间复杂度为（m+n）；我们通过之前的分析可以知道Dinic算法时间复杂度理论的上界是O(n2*m)，其中m为弧的数目，n是迭代次数，是多项式算法。邻接表表示图，空间复杂度为（m+n）。
Ford-Fulkerson算法的实际运行效率也取决于如何确定增广路径。如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同；Edmonds-Karp算法的实际运行效率远高于Ford-Fulkerson算法；Dinic算法是这3种算法中效率最高的，因为它兼取了前两种算法的优点,在分层时用宽度优先法，寻求增广路径时用深度优先策略。
4.结论
本文研究了几种网络最大流算法，即Ford-Fulkerson算法、Edmonds-Karp修正算法以及Dinic算法。这些算法的理论基础是图论知识，并以此来讨论最大流问题。最大流问题是一类应用广泛的问题，20世纪50年代的富克逊、福特建立的网络流理论是网络应用的重要组成部分[10]。最大流问题的核心依据是Ford-Fulkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson算法、Edmonds-Karp修正算法、Dinic算法等算法，本论文介绍了这3种算法，并实现了各个算法。
各算法的优劣各不相同，Ford-Fulkerson算法是最基础的算法，由Fulkerson和Ford提出，但是有局限性，只是采用了深度优先策略，如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同；Edmonds和Karp针对该算法增广路径选取的任意性这一缺点对它做出了修正，产生了Edmonds-Karp修正算法，它是用宽度优先取代了深度优先；而Dinic算法则兼取前两种算法的优点，在分层时用宽
度优先法，而寻求增广路径时则采用深度优先策略，它是这三种算法中效率最高的算法。
最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便,比如说电力传输问题，供销通路问题，矿井通风网络的确定，铁路货运列车的最优调度等。在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成一个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。
参考文献：
[1] 顾基发，钱颂迪，田丰，等.运筹学［M］.北京:清华大学出版社，2006:213-215 [2] 徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2005:176-183 [3] 王桂平等.图论算法理论、实现及应用［M］.北京: 北京大学出版社，2011:214-216 [4] 张宪超，陈国良，万颖瑜.网络最大流问题研究进展［J］.计算机研究与进展，2003，40（9）：1281-1292
[5] 田丰，马仲蕃. 图与网络流理论［M］.北京：科学出版社，1987:178-184
[6] 左孝凌、李为鑑、刘永才.离散数学［M］.上海:上海科学技术文献出版社，1982:271-272 [7] Bondy JA, Mutry USR.Graph Theory with Applications［J］.IEEE Graph Theory, 1976:1-264 [8] Goldberg A V,Ros S. Beyond the flow decomposition barrier［J］.Jassoc Compute Mach,1998,45(5):783-797
[9] 赵礼峰，白睿，宋常城求解网络最大流问题的标号算法［J］.计算机技术与发展，2011，21（12）：114-115
[10] 凌永发，徐宗本.一种求解网络最大流问题的算法［J］.计算机科学，2006，33（6）：39-41 [11] 谢凡荣. 运输网络中求最小费用最大流的一个算法［J］.运筹与管理，2000（4），33-38 1281-1292
[12] Minoux M.On robust maximum flow with polyhedral umcertainty set［J］.Optim Lett.2009(3):367-376
[13] Ahuja R K,Magnanti T L,Orlin J B. Network Flows:Theory,Algorithms and Applications［M］.New Jersey:Prentice Hall,2000.134-151
[14] Zhang Xianhao. Research on the maximun network flow problem［J］.Journal of Computer
Research and Development,2003,40(9):1281-1292
[15] 赵礼峰，陈华，宋常城，等.基于一个网络图最大流算法的改进［J］.计算机技术与发展，2010，20（12）：162-165
网络流：最小费用最大流(最简单的算法)
网络流：最小费用最大流（最简单的算法）
最小费用流在 OI 竞赛中应当算是比较偏门的内容，但是 NOI2008 中 employee 的突然出现确实让许多人包括 zkw 自己措手不及。可怜的 zkw 当时想出了最小费用流模型，可是他从来没有实现过，所以不敢写，此题 0 分。zkw 现在对费用流的心得是：虽然理论上难，但是写一个能 AC 题的费用流还算简单。先贴一个我写的 employee 程序：只有不到 70 行，费用流比最大流还好写～
程序代码:C++
#include
#include
using namespace std;
const int maxint=~0U>>1;
int n,m,pi[550]={0},cost=0;
bool v[550]={0};
struct etype
{
int t,c,u;
etype *next,*pair;
etype(){}
etype(int t_,int c_,int u_,etype* next_):t(t_),c(c_),u(u_),next(next_){} void* operator new(unsigned,void* p){return p;}
} *e[550],*eb[550];
int aug(int no,int m)
{
if(no==n)return cost+=pi[1]*m,m;
v[no]=true;
for(etype *&i=e[no];i;i=i->next)
if(i->u && !v[i->t] && pi[i->t]+i->c==pi[no])
if(int d=aug(i->t,mu?m:i->u))
return i->u-=d,i->pair->u+=d,d;
return 0;
}
bool modlabel()
{
int d=maxint,c;
for(int i=1;i
for(etype *j=eb[i];j;j=j->next)if(j->u && !v[j->t])
if((c=j->c-pi[i]+pi[j->t])
if(d==maxint)return false;
for(int i=1;i
return true;
}
int main()
{
freopen("costflow.in","r",stdin);
freopen("costflow.out","w",stdout);
scanf("%d %d",&n,&m);
etype *Pe=new etype[m+m];
while(m--)
{
int s,t,c,u;
scanf("%d%d%d%d",&s,&t,&u,&c);
e[s]=new(Pe++)etype(t, c,u,e[s]);
e[t]=new(Pe++)etype(s,-c,0,e[t]);
e[s]->pair=e[t];
e[t]->pair=e[s];
}
memmove(eb,e,sizeof(e));
do do memset(v,0,sizeof(v));
while(aug(1,maxint));
while(modlabel());
printf("%d\n",cost);
return 0;
}
程序代码:CB大牛翻译的PASCAL
var
n,m,i,l,s,t,c,cost,u:longint;
v:array[0..600]of boolean;
dis:array[0..600]of longint;
e_n,e_t,e_c,e_u,e_p,e_x:array[0..250000]of longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b);
exit(a);
end;
procedure addedge(s,t,c,u,k:longint);
begin
inc(l);
e_n[l]:=e_n[s];
e_n[s]:=l;//下一条边
e_t[l]:=t;//边的另一端
e_c[l]:=c;//边的费用
e_u[l]:=u;//边的容量
e_p[l]:=l+k;//对应的边
end;
procedure build(s,t,c,u:longint);
begin
addedge(s,t,c,u,1);
addedge(t,s,-c,0,-1);
end;
function aug(no,m:longint):longint;
var
i,d:longint;
begin
if no=n then begin
inc(cost,m*dis[1]);
exit(m);
end;
v[no]:=true;
i:=e_x[no];
while i0 do begin
if (e_u[i]>0)and(not v[e_t[i]])and(dis[e_t[i]]+e_c[i]=dis[no]) then begin
d:=aug(e_t[i],min(m,e_u[i]));
if d>0 then begin
dec(e_u[i],d);
inc(e_u[e_p[i]],d);
e_x[no]:=i;
exit(d);
end;
end;
i:=e_n[i];
end;
e_x[no]:=i;
exit(0);
end;
function modlabel:boolean;
var
d,i,j:longint;
begin
d:=maxlongint;
for i:=1 to n do if v[i] then begin
j:=e_n[i];
while j0 do begin
if (e_u[j]>0)and(not v[e_t[j]])and(e_c[j]-dis[i]+dis[e_t[j]]
j:=e_n[j];
end;
end;
if d=maxlongint then exit(true);
for i:=1 to n do if v[i] then begin
v[i]:=false;
inc(dis[i],d);
end;
exit(false);
end;
begin
assign(input,'coflow.in');reset(input);
assign(output,'coflow.out');rewrite(output);
readln(n,m);
l:=n;
for m:=m downto 1 do begin
readln(s,t,u,c);
build(s,t,c,u);
end;
repeat
for i:=1 to n do e_x[i]:=e_n[i];
while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0);
until modlabel;
writeln(cost);
close(output);
end.
这里使用的是连续最短路算法。最短路算法？为什么程序里没有 SPFA？Dijkstra？且慢，先让我们回顾一下图论中最短路算法中的距离标号。定义
为点
的距离标号，任何一个最短路算法保证，算法结束时对任意指向顶点
、从顶点
出发的边满足 （条件1），且对于每个
存在一个
使得等号成立（条件2）。换句话说，任何一个满足以上两个条件的算法都可以叫做最短路，而不仅仅是 SPFA、Dijkstra，算法结束后，恰在最短路上的边满足
。
在最小费用流的计算中，我们每次沿
的路径增广后都不会破坏条件 1，但是可能破坏了条件 2。不满足条件 2 的后果是什么呢？使我们找不到每条边都满足
新的增广路。只好每次增广后使用 Dijkstra，SPFA 等等算法重新计算新的满足条件 2 的距离标号。这无疑是一种浪费。KM 算法中我们可以修改不断修改可行顶标，不断扩大可行子图，这里也同样，我们可以在始终满足条件 1 的距离标号上不断修改，直到可以继续增广（满足条件 2）。
回顾一下 KM 算法修改顶标的方法。根据最后一次寻找交错路不成功的 DFS，找到
，左边的点增加
，右边的点减少
。这里也一样，根据最后一次寻
找增广路不成功的 DFS，找到
可以证明，这样不会破坏性质 1，而且至少有一条新的边进入了
，所有访问过的点距离标号增加
。的子图。
算法的步骤就是初始标号设为
，不断增广，如果不能增广，修改标号继续增广，直到彻底不能增广：源点的标号已经被加到了
。
这样我们得到了一个简单的算法，只需要增广，改标号，各自只有 7 行，不需要 BFS，队列，SPFA，编程复杂度很低。由于实际的增广都是沿最短路进行的，所以理论时间复杂度与使用 SPFA 等等方法的连续最短路算法一致，但节省了 SPFA 或者 Dijkstra 的运算时间。实测发现这种算法常数很小，速度较快，employee 这道题所有数据加在一起耗时都在 2s 之内
最小费用流的各种转化
不少同学认为消圈算法比增广路算法使用面广，可以有负边，负圈，每个点都能有盈余亏空等等。实际上增广路算法也是一样的。
以下讨论中 为盈余量， 为费用， 为容量。
1).最小费用(可行)流 最小费用最大流
建立超级源 和超级汇
，对顶点
，若
，之后求从
添加边
，若
添加边
到
的最小费用最大流，如果流量等于
，就存在可行流，
残量网络已在原图上求出。
2).最小费用最大流 最小费用(可行)流
连边
，所有点
有
，然后直接求。
3).最小费用(可行)流中负权边的消除
直接将负权边满流。
4.)最小费用最大流中负权边的消除
先连边
，使用(3.)中的方法消除负权边，使用(1.)中的方法求出最小费用(可行)流，之后距离标号不变，再求最小费用最大流；注意此时增广费用不能机械使用源点的标号——应该是源点汇点标号之差。
p.s.评测说明，最小费用流简单算法中的方法速度比 SPFA 的实现快好多，推荐大家竞赛时使用
网络流：最小费用最大流(PASCAL代码)
具体的参见我的网络流总结
这里说一种简洁高效的算法，来自ZKW神牛的原创。性价比高，适合在竞赛使用。
即采用距离标号法，若能增广则无限增广，反之更新距离标号，直到无法更新为止。
const maxn=501; maxm=240001;
type gtp=record y,d,c,op,next:longint; end;
//========================================================
var n,m,tot,st,ed,ans:longint;
g:array[0..maxm] of gtp;
first,now,dis:array[0..maxn] of longint;
v:array[0..maxn] of boolean;
//========================================================
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
//========================================================
procedure add(x,y,d,c,t:longint); {存边表}
begin
inc(tot);
g[tot].y:=y; g[tot].d:=d; g[tot].c:=c;
g[tot].op:=tot+t; g[tot].next:=first[x]; first[x]:=tot;
end;
//========================================================
procedure init;
var i,x,y,d,c:longint;
begin
fillchar(first,sizeof(first),0);
readln(n,m); tot:=0; st:=1; ed:=n; ans:=0;
for i:=1 to m do
begin
readln(x,y,d,c); {x点y点，容量，费用}
add(x,y,d,c,1); add(y,x,0,-c,-1); {正反向都存}
end;
end;
//========================================================
function aug(x,flow:longint):longint; {寻找增广路}
var y,t,tmp:longint;
begin
if x=ed then {找到增广路，增加流量}
begin
inc(ans,flow*dis[st]);
exit(flow);
end;
t:=now[x]; v[x]:=true;
while t0 do
begin
y:=g[t].y;
if (g[t].d>0)and(not v[y])and(dis[x]=dis[y]+g[t].c) then {满足容量、未被访问（这里是一个优化）、距离标号关系}
begin
tmp:=aug(y,min(g[t].d,flow)); {继续增广}
if tmp>0 then {若增广成功}
begin
dec(g[t].d,tmp); inc(g[g[t].op].d,tmp); {更新容量值}
now[x]:=t; {更新当前弧}
exit(tmp);
end;
end;
t:=g[t].next;
end;
now[x]:=0; {小优化}
exit(0);
end;
//========================================================
function modlabel:boolean; {修改距离标号}
var tmp,y,i,t:longint;
begin
tmp:=maxlongint;
for i:=1 to n do
if v[i] then {若某边为true，则距离标号已经不合格}
begin
t:=first[i];
while t0 do
begin
y:=g[t].y;
if (g[t].d>0)and(not v[y])and(dis[y]+g[t].c-dis[i]
tmp:=dis[y]+g[t].c-dis[i]; {取最小值}
t:=g[t].next;
end;
end;
if tmp=maxlongint then exit(true); {无法修复距离标号}
for i:=1 to n do {若能修复，则修复距离标号}
if v[i] then
begin
inc(dis[i],tmp);
v[i]:=false;
end;
exit(false);
end;
//========================================================
procedure main;
var i:longint;
begin
fillchar(dis,sizeof(dis),0);
repeat
for i:=1 to n do now[i]:=first[i];
while aug(st,maxlongint)>0 do fillchar(v,sizeof(v),false); {若能增广则无限增广} until modlabel; {直到无法修复距离标号}
writeln(ans);
end;
//========================================================
begin
assign(input,'costflow.in'); reset(input);
assign(output,'costflow.out'); rewrite(output);
init;
main; then
close(input); close(output); end.
转载请注明出处范文大全网 » 基于栈的网络最大流算法
大腿无名指
