《最大流算法.ppt》由会员分享，可在线阅读，更多相关《最大流算法.ppt（32页珍藏版）》请在三一文库上搜索。
1、网络流初步, 最大流算法 最小费用最大流 最大流最小割定理,最大流算法,网络流之一,问题：问从S到T的最大水流量是多少？,实例：,有一自来水管道输送系统，起点是S，目标是T，途中经过的管道都有一个最大的容量。,1 S,4,3,2,5,6 t,7,3,4,8,4,2,4,6,4,6,2,2,2,4,4,6,最大水流量是10,一、网络流的定义,有唯一的一个源点S（入度为0：出发点） 有唯一的一个汇点 T（出度为0：结束点） 图中每条弧 (u, v) 都有一非负容量 c ( u, v ),有向图 G = ( V, E )中：,满足上述条件的图G称为网络流图。 记为： G = ( V, E ，C),1
2、、可行流,每条弧 ( u, v )上 给定一个实数f(u,v),满足：有 0 = f ( u, v ) = c( u, v ),则f(u,v)称为弧( u, v )上的流量。 如果有一组流量满足条件： 源点s ： 流出量 = 整个网络的流量 汇点t ： 流入量 =整个网络的流量 中间点：总流入量 = 总流出量 那么整个网络中的流量成为一个可行流。,区分：容量和流量,一个可行流：5,一个可行流：7,图1,图2,2、最大流,在所有的可行流中， 流量最大的一个流的流量 如： 图2中可行流7也是最大流。 最大流可能不只一个。,二、最大流算法,步骤：（1）如果存在增广路径,就找出一条增广路径 （2）然后
3、沿该条增广路径进行更新流量 （增加流量）,Ford-Fulkerson （福特-福克森）算法：,1、增广路径,从 s 到 t 的一条简单路径，若边 ( u, v ) 的方向与该路径的方向一致，称 ( u, v ) 为正向边，方向不一致时称为逆向边。,简单路：13 245中。 （1，3）（2，4）（4，5）是正向边。（3，2）是逆向边。,1,2,4,3,5,6,4,2,3,4,5,1,2,4,3,5,6,4,2,3,4,5,若路径上所有的边满足： 所有正向边有：f ( u, v ) 0 则称该路径为一条增广路径(可增加流量),增广路径：,两条增广路径： 135 13 245,增加流量=？,2、沿
4、增广路径增广,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,样例：,开始流量为:sum=0,1、一条增广路径: 1235 d=min4,2,4 =2 增加流量: 2 Sum=2,2、一条增广路
5、径: 1245 d=min4-2,3,5 =2 增加流量: 2 Sum=2+2=4,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2-1=1,2,1,2,4,3,5,4,2,3,4,5,2,2,2,3、一条增广路径: 1 2 4 5 d=min6,2,3-2,5-2 =1 增加流量: 1 Sum=4+1=5,1,1,1,2-3减少，加到- -3减的由-补充,4、一条增广路径: 1 5 d=min6-1,4-2 =2 增加流量:
6、 2 Sum=5+2=7,1,2,4,3,5,6,4,2,3,4,5,2,2-1=1,2,1,2,4,3,5,4,2,3,4,2,2,2,1,1,1,定理： 可行流 f 为最大流，当且仅当不存在关于f 的增广路径 证：若 f 是最大流，但图中存在关于 f 的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f 是最大流矛盾。所以，最大流不存在增广路径。,Ford-Fulkerson方法(增广流)求最大流 （福特-福克森）,步骤：（1）如果存在增广路径,就找出一条增广路径 DFS,BFS（2）然后沿该条增广路径进行更新流量 （增加流量）,While 有增广路径 do 更新该路径的流量 迭
7、代算法,c u, v ：容量 f u, v ：流量 Bi：保存找到的增广路径，记录路径上结点i的前驱结点。 Sum：最大流量。 假定：1是源点S；n是汇点T。,算法的实现：,function findflow(k:integer):boolean; 找结点k的后继结点i var i:integer; begin if k=n then exit(true); 找到了一条增广路径 for i:=1 to n do if(bi=-1) and(ck,i-fk,i0)or(fi,k0) then begin bi:=k; if findflow(i) then exit(true); end; ex
8、it(false); end;,1）：DFS找增广路径,2） procedure addflow;/沿增广路径增广（增加流量）,d:=maxint; 增量 i:=n; 沿增广路径的终点向起点反向求d while bi0 do begin if cbi,i0 then d:=min(d,cbi,i-fbi,i); 正向边 if ci,bi0 then d:=min(d,fi,bi); 逆向边 i:=bi; end; i:=n; while bi0 do 逆向更新每条边的流量 begin if cbi,i0 then inc(fbi,i,d); 正向边 if ci,bi0 then dec(fi,
9、bi,d); 逆向边 i:=bi; end; inc(sum,d); 总流量增加d,主程序： for i:=1 to n do bi:= -1; 初始化增广路径 b1:=0; while findflow(1) do 增广流 begin addflow; for i:=1 to n do bi:=-1; b1:=0; end; writeln(sum); 输出最大流 for i:=1 to n do 输出每条边的流量 for j:=1 to n do if fi,j0 then writeln(i,-,j, ,fi,j);,优化,残留网络 d 的设置： 若存在 ( u, v ) 则 d ( u
10、, 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,深搜找增广路径过程 function find( k:integer ):boolean; if k=n then exit(true);
11、 for i:=1 to n do if (bi= -1) and (dk,i0) then bi:=k; if find(i) then exit(true); / 此处bi不需要变回-1 exit(false); / b1=0; b2 n= -1; 主函数中调用find(1),广搜找增广路径过程 function bfsbfs:boolean; a 是广搜队列 for i:=1 to n do bi:=-1; b 是前驱 b1:=0; a1:=1; open:=0; closed:=1; while open0) then inc(closed); aclosed:=i; bi:=k; i
12、f i=n then exit(true); 找到增广路 exit(false); 没找到增广路,增广过程 min:=maxint; i:=n; while bi0 (i1) do /逆向求增加流min if mindbi,i then min:=dbi,i; i:=bi; i:=n; while bi0 (i1) do/ /逆向修改流量 dec(dbi,i,min); inc(di,bi,min); i:=bi; inc(sum,min); sum是总流量,问题1：奶牛的新年晚会,奶牛们要举办一次别开生面的新年晚会。每头奶牛会做一些不同样式的食品（单位是盘）。到时候他们会把自己最拿手的不超过
13、k样食品各做一盘带到晚会，和其他奶牛一起分享。但考虑到食品太多会浪费掉，他们给每种食品的总盘数都规定了一个不一定相同的上限值。这让他们很伤脑筋，究竟应该怎样做，才能让晚会上食品的总盘数尽量的多呢？,例如：有4头奶牛，每头奶牛最多可以带3盘食品。一共有5种食品，它们的数量上限是2、2、2、2、3。奶牛1会做食品14，奶牛2会做食品25，奶牛3会做食品1、2、4，奶牛4会做食品13。那么最多可以带9盘食品到晚会上。即奶牛1做食品24，奶牛2做食品35，奶奶3做食品1、2，奶牛4做食品1。这样，4种食品各有2、2、2、2、1盘。,奶牛,食品,边：S奶牛, 保证每头奶牛带的食品的最大量。 边：食品T, 保证每种食品的最大数量。 食品的总盘数最大值=S到T的最大流,奶牛,食品,S到T的最大流=9,应用,求二分图的最大匹配 利用网络流建模 所有边的容量都是1,