资源描述：
《最大流算法资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最大流算法最大流算法网络流之一问题：问从S到T的最大水流量是多少？1S43256t73484246实例：有一自来水管道输送系统，起点是S，目标是T，途中经过的管道都有一个最大的容量。1S43256t7348424646222446最大水流量是10一、网络流的定义有唯一的一个源点S（入度为0：出发点）有唯一的一个汇点T（出度为0：结束点）图中每条弧(u,v)都有一非负容量c(u,v)有向图G=(V,E)中：满足上述条件的图G称为网络流图。记为：G=(V,E，C)1、可行流◆每条弧(u,v)上给定一个实数f(u,
2、v),满足：有0<=f(u,v)<=c(u,v),则f(u,v)称为弧(u,v)上的流量。◆如果有一组流量满足条件：源点s：流出量=整个网络的流量汇点t：流入量=整个网络的流量中间点：总流入量=总流出量那么整个网络中的流量成为一个可行流。区分：容量和流量124356423454121243542333112435642345411243542353334一个可行流：5一个可行流：7图1图22、最大流在所有的可行流中，流量最大的一个流的流量如：图2中可行流7也是最大流。最大流可能不只一个。二、最大流算法步骤：（
3、1）如果存在增广路径,就找出一条增广路径（2）然后沿该条增广路径进行更新流量（增加流量）◆Ford-Fulkerson（福特-福克森）算法：1、增广路径从s到t的一条简单路径，若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边，方向不一致时称为逆向边。简单路：13245中。（1，3）（2，4）（4，5）是正向边。（3，2）是逆向边。1243564234512435642345若路径上所有的边满足：①所有正向边有：f(u,v)0则称该路径为一条
4、增广路径(可增加流量)增广路径：两条增广路径：135132451243564234522212435642345222增加流量=？2、沿增广路径增广1）先设d为为正无穷(可增加流，余流量)若(u,v)是正向边d=min(d,c(u,v)–f(u,v))若(u,v)是逆向边d=min(d,f(u,v))2）对与该增广路径上的边若(u,v)是正向边，f(u,v)=f(u,v)+d;若(u,v)是逆向边，f(u,v)=f(u,v)–d;增广后，总流量增加了d12435642345样例：开始流量为:sum
5、=01、一条增广路径:1235d=min{4,2,4}=2增加流量:2Sum=212435642345222124356423452、一条增广路径:1245d=min{4-2,3,5}=2增加流量:2Sum=2+2=412435642345222124356423452221243564234522212435642345222124356423452221243564234522-1=1212435423452223、一条增广路径:1３245d=min{6,2,3-2,5-2}=1增加流
6、量:1Sum=4+1=51112->3减少１，加到２->４２->3减的１由１->３补充１4、一条增广路径:1３5d=min{6-1,4-2}=2增加流量:2Sum=5+2=71243564234522-1=121243542342221111243564234522-1=12124354234522211122定理：可行流f为最大流，当且仅当不存在关于f的增广路径证：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。所以，最大流不存在增广路径。◆Fo
7、rd-Fulkerson方法(增广流)求最大流（福特-福克森）步骤： （1）如果存在增广路径,就找出一条增广路径DFS,BFS （2）然后沿该条增广路径进行更新流量（增加流量）While有增广路径do更新该路径的流量迭代算法c[u,v]：容量f[u,v]：流量B[i]：保存找到的增广路径，记录路径上结点i的前驱结点。Sum：最大流量。假定：1是源点S；n是汇点T。算法的实现：functionfindflow(k:integer):boolean;{找结点k的后继结点i}vari:integer;beginif
8、k=nthenexit(true);{找到了一条增广路径}fori:=1tondoif(b[i]=-1)and((c[k,i]-f[k,i]>0)or(f[i,k]>0))thenbeginb[i]:=k;iffindflow(i)thenexit(true);end;exit(false);end;1）：DFS找增广路径2）procedureaddflow;//沿增广路径增广（增加流量）d:=ma
