网络流算法设计.ppt

Copyright 2000, Kevin Wayne 网络流（Network-Flow ) 主要内容 最大流算法 最小费用流算法 网络流算法应用举例 皇家空军飞行员问题 最小逃脱问题 最佳航空路线问题 背景 许多系统包含了流量问题。 例如： 公路系统中有车辆流， 控制系统有信息流， 供水系统中有水流， 金融系统中有现金流等。 图为连接产地V1和销地V7的交通网,边上 的数字表示这条边的最大通过量Cij(容量),括号里的数字表示实际通过量fij(流量)。 所有括号里的数fij (i=1,…,7)给出一种  运输方案。 网络与流 网络 G=(V,E) ,V={1,2,…,n}是一个简单有向图.V中有一顶点s称为源，另一顶点t称为汇。对于有向图G的每条边(i,j)∈E,对应有一个值capa(i,j)≥0,称为边的容量。 这种有向图G称作一个网络，记为G=(V,E,capa)。 网络与流 流量（flow) 对于给定的网络G, 从源点出来的“货物”, 经过网络上的有向边, 最后流入汇点的“货物”称为流量, 而每一条边( vi vj ) 流过的流量,记为f ( vi vj ) (或f ( i j) )称为边( vi vj ) 的流。 网络与流 流量（flow) 对给定的网络G, 若每条边上的流都知道, 即相当于在G 的边集E上定义了一个函数(即G上所有边的流的全体) F = { f ( vi vj) | vi , vj ∈ V } 则称F 是网络G 的流。 显然,边( vi vj ) 的流不能超过该边的容量 , 因此有0 ≤ f ( ( vi vj ) ≤ c (vi vj ) 满足上式的网络称为相容网络。 网络与流 可行流 满足以下条件的流f称为可行流： 容量限制：对每条边(i,j)∈E, 0≤f(i,j) ≤capa(i,j); 平衡条件： 对中间点i： 对源s: 对汇t: 最大流问题 给一流网络G，源 s以及汇t。求一个网络的流{f(i,j)},使其流量|f|达到最大且是可行流。 前向边和后向边 可改进路（增广路， Augmenting Path) 对于源s到汇t的一条简单路，如果路上的每条边(i,j)的可改进量均大于0,则称这条路为一条可改进路(增广路)。 所有边的可改进量的最小值为可改进路的改进量 调整该路径的流量 确定改进量a: 先看P+={(V1,V2),(V2,V4),(V4,V6)} c(1,3)-f(1,3)=8-2=6 c(2,4)-f(2,4)=4-0=4 c(4,6)-f(4,6)=7-2=5 再看P的后向边集合p-={(V2,V3)}, f(2,3)=2 因此改进量a至多取2。使改进后的前向边流量增加，又使改进后的后向边的流量不为负。 改进后流量增为2。 求解最大流 寻找增广路 设f是一个可行流，p是从s到t的一条路，若： 在p的所有前向边(i,j)上，0≤f(i,j)capa(i,j). 非饱和边 改进量为a=capa(i,j)-f(i,j)。 (2) 在p的所有后向边(i,j)上，0f(i,j)≤capa(i,j). 非零流边 改进量为a=f(i,j)。 则称P为关于可行流f的一条增广路。 所有边的可改进量的最小值为增广路p的改进量 为寻找增广路，可定义剩余网络，剩余网络中存在从源到汇的路径，则这条路径就是增广路。 流的剩余网络与原始流网络G有相同顶点，原始网络每条边（i，j)在剩余网络中对应一条或两条边： 令（i，j)的流量为f,容量为c。 （1）若(i,j)是不饱和边，fc,则剩余网络中包含边（i，j),其容量为c-f （2）若(i,j)是非零流边，f0,则剩余网络中包含边（j，i),其容量为f 最大流增广路算法(Ford Fulkerson) 设f是网络G的一个可行流，如果不存在从s到t关于f的可改进路p，则f一定是最大流。 增广路方法： （1）置f=0为初始可行流； （2）while (存在从s到t关于f的可改进路）do