算法分析与设计最大流问题Word格式文档下载.docx
《算法分析与设计最大流问题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《算法分析与设计最大流问题Word格式文档下载.docx（20页珍藏版）》请在冰点文库上搜索。
4
3
2
5
6t
7
8
6
最大水流量是10
3算法论述
3.1、可行流
每条弧（u,v）上给定一个实数f（u,v）,满足：
有0<
=f（u,v）<
=c（u,v）,则f（u,v）称为弧（u,v）上的流量。
如果有一组流量满足条件：
源点s：
流出量=整个网络的流量
汇点t：
流入量=整个网络的流量
中间点：
总流入量=总流出量那么整个网络中的流量成为一个可行流。
区分：
容量和流量
1
一个可行流：
7
图1
图2
3.2最大流
在所有的可行流中，流量最大的一个流的流量
如：
图2中可行流7也是最大流。
最大流可能不只一个。
3.3最大流算法
Ford-Fulkerson（福特-福克森）算法：
步骤：
（1）如果存在增广路径,就找出一条增广路径
（2）然后沿该条增广路径进行更新流量
（增加流量）
3.3.1增广路径
从s到t的一条简单路径，若边（u,v）的方向与该路径的方向一致，称（u,v）为正向边，方向不一致时称为逆向边。
简单路：
13245中。
（1，3）（2，4）（4，5）是正向边。
（3，2）是逆向边。
增广路径：
若路径上所有的边满足：
①所有正向边有：
f（u,v）<
c（u,v）
②所有逆向边有：
f（u,v）>
0
则称该路径为一条增广路径（可增加流量）
两条增广路径：
135
13245
增加流量=？
3.3.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;
增广后，总流量增加了d
3.3.3样例：
开始流量为:
sum=0
一条增广路径:
1235，d=min{4,2,4}=2，增加流量:
2
Sum=2
1245，d=min{4-2,3,5}=2，增加流量:
Sum=2+2=4
1３245，d=min{6,2,3-2,5-2}=1
增加流量:
1，Sum=4+1=5
1３5，d=min{6-1,4-2}=2增加流量:
Sum=5+2=7
3.3.4定理：
可行流f为最大流，当且仅当不存在关于f的增广路径
证：
若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。
所以，最大流不存在增广路径。
Ford-Fulkerson方法（增广流）求最大流（福特-福克森）：
步骤：
（1）如果存在增广路径,就找出一条增广路径DFS,BFS
（2）然后沿该条增广路径进行更新流量增加流量）
While有增广路径do更新该路径的流量
迭代算法
3.3.5算法的实现：
c[u,v]：
容量
f[u,v]：
流量
B[i]：
保存找到的增广路径，记录路径上结点i的前驱结点。
Sum：
最大流量。
假定：
1是源点S；
n是汇点T。
1）：
DFS找增广路径
functionfindflow（k:
integer）:
boolean;
{找结点k的后继结点i}
vari:
integer;
begin
ifk=nthenexit（true）;
{找到了一条增广路径}
fori:
=1tondo
if（b[i]=-1）and（（c[k,i]-f[k,i]>
0）or（f[i,k]>
0））then
b[i]:
=k;
iffindflow（i）thenexit（true）;
end;
exit（false）;
2）procedureaddflow;
//沿增广路径增广（增加流量）
d:
=maxint;
{增量}
i:
=n;
{沿增广路径的终点向起点反向求d}
whileb[i]<
>
0do
ifc[b[i],i]>
0thend:
=min（d,c[b[i],i]-f[b[i],i]）;
{正向边}
ifc[i,b[i]]>
=min（d,f[i,b[i]]）;
{逆向边}
=b[i];
0do{逆向更新每条边的流量}
0theninc（f[b[i],i],d）;
{正向边}
ifc[i,b[i]]>
0thendec（f[i,b[i]],d）;
{逆向边}
inc（sum,d）;
{总流量增加d}
主程序：
=1tondob[i]:
=-1;
{初始化增广路径}
b[1]:
=0;
whilefindflow
（1）do{增广流}
addflow;
=-1;
writeln（sum）;
{输出最大流}
=1tondo{输出每条边的流量}
forj:
iff[i,j]>
0thenwriteln（i,'
-->
'
j,'
'
f[i,j]）;
3.3.6优化
残留网络d的设置：
若存在（u,v）则
d（u,v）=c（u,v）–f（u,v）
d（v,u）=f（u,v）
d（u,v）是从u到v能增加的最大流量
理解:
（u,v）的流量为f（u,v）,作为正向边还可以增加的量是
c（u,v）–f（u,v），作为逆向边，还可以增加的流量为：
f（u,v）。
增广路上正向边流量增加，逆向边增加流量减少。
d（u,v）=c（u,v）
d（v,u）=0
深搜找增广路径过程
functionfind（k:
integer）:
if（b[i]=-1）and（d[k,i]>
0）then
[b[i]:
iffind（i）thenexit（true）;
//此处b[i]不需要变回-1]
//b[1]=0;
b[2~n]=-1;
主函数中调用find
（1）
广搜找增广路径过程
functionbfsbfs:
a是广搜队列
b是前驱
a[1]:
=1;
open:
closed:
whileopen<
closeddo
[inc（open）;
k:
=a[open];
=1tondod是残余流量
[inc（closed）;
a[closed]:
=i;
ifi=nthenexit（true）;
找到增广路]
]
没找到增广路
增广过程
min:
0（i<
1）do//逆向求增加流min
[ifmin>
d[b[i],i]thenmin:
=d[b[i],i];
]
1）do////逆向修改流量
[dec（d[b[i],i],min）;
inc（d[i,b[i]],min）;
inc（sum,min）;
sum是总流量
4算法应用
在现实生活中，在实际的网络中，网络的结点和边都是有容量限制的.很多情况下我们需要知道在一个有容量限制的网络中两个指定结点（分别称为源点和汇点）之间最多能传输多少流量，并确定达到这个最大流量的传输策略.网络最大流问题（简称最大流问题）就是描述这个问题的数学模型.
最大流问题是网络流理论的重要组成部分，它是一个经典的组合优化问题，同时也可以看做是特殊的线性规划问题.除了解决实际网络中的问题以外，最大流问题在电力、交通、通信、计算机网络等工程领域和物理、化学等科学领域有着广泛的应用，许多其它的组合优化问题也可以通过最大流问题求解。
限制条件下网络最大流问题在包含流量的系统中有着广泛的应用，例如在公路系统中的车流、控制系统中的信息流等等。
如何在现有条件下使网络流量能达到最大流量，并如何进行流量分配是一个具有现实意义的问题。
随着生产和科学技术的发展，网络最小费用最大流算法面临新的问题和挑战。
例如在VLSI、光网路由等领域，往往涉
及到一些节点和边都有容量的有向平面网络。
升级会员 