资源描述：
《最小费用最大流》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最小费用最大流Spfa实现概念网络流图论中的一种理论与方法，研究网络上的一类最优化问题。所谓网络或容量网络指的是一个连通的赋权有向图D＝(V、E、C)，其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送
2、到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。网络流问题定义1设G=(V,E)为有向图,在V中指定一点称为发点(记为vs),和另一点称为收点(记为vt),其余点叫做中间点.对每一条边vivj∈E,对应一个非负实数Cij,称为它的容量.这样的G称为容量网络,简称网络,记作G=(V,E,C).定义2网络
3、G=(V,E,C)中任一条边vivj有流量fij,称集合f={fij}为网络G上的一个流.满足下述条件的流f称为可行流：①(限制条件)对每一边vivj,有0≤fij≤Cij;②(平衡条件)对于中间点vk有∑fik=∑fkj,即中间点vk的输入量=输出量.如果f是可行流,则对收、发点vt、vs有∑fsi=∑fjt=Wf,即从vs点发出的物质总量=vt点输入的量.Wf称为网络流f的总流量.上述概念可以这样来理解,如G是一个运输网络,则发点vs表示发送站,收点vt表示接收站,中间点vk表示中间转运站,可行流fij表示某条运输线上通过的
4、运输量,容量Cij表示某条运输线能承担的最大运输量,Wf表示运输总量.可行流总是存在的.比如所有边的流量fij=0就是一个可行流(称为零流).网络流算法寻找增广路，并根据增广路修改流量。重复这一步骤，直到不再存在增广路。如果需要在此基础上求最小费用最大流，只需从增广路的选择上着手。可改进路(可增广路） 给定一个可行流f。若fij=cij，称为饱和弧；否则称为非饱和弧。若fij=0，称为零流弧；否则称为非零流弧。 定义一条道路P，起点是S、终点是T。把P上所有与P方向
5、一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。4248473621STV1V2V3V4譬如在图中，P=(S,V1,V2,V3,V4,T)，那么P+={,,,}P-={}给定一个可行流f，P是从S到T的一条道路，如果满足：那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。所谓最大流问题就是在容量网络中,寻找流量最大的
6、可行流.譬如对上图而言，它的最大流如下：3244053021STV1V2V3V4最大流图在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。 对可改进路P上的弧，分为两种情况讨论： 第一种情况：∈P+，可以令fij增加一个常数delta。必须满足fij+delta≤cij，即delta≤cij–fij。 第二种情况：∈P-，可以令fij减少一个常数delta。必须满足fij-delta≥0，即del
7、ta≤fij根据以上分析可以得出delta的计算公式：因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，∴delta>0。 容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta>0）。 因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？答案是肯定的。最大流算法算法思想:最大流问题实际上是求一可行流{f
8、ij}，即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所
