浅谈网络流算法与几种模型转换

《浅谈网络流算法与几种模型转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈网络流算法与几种流模型吴迪1314010425摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。关键词：网络流Edmonds-Karp最大流dinic最大流最小割网络流模型最小费用最大流正文：图论中的一种理论与方法，研究网络上的一

2、类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图D=（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图

3、看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的

4、方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。先来看一个实例。现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下：每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：1、有且仅有一个顶点S，它的入度为零，即d-(S)=0，这个顶点S便称为源点，或称为发点。

5、2、有且仅有一个顶点T，它的出度为零，即d+(T)=0，这个顶点T便称为汇点，或称为收点。3、每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。三个基本的性质:如果C代表每条边的容量F代表每条边的流量一个显然的实事是F小于等于C不然水管子就爆了这就是网络流的第一条性质容量限制(CapacityConstraints):F

6、>≤C再考虑节点任意一个节点流入量总是等于流出的量否则就会蓄水或者平白无故多出水这是第二条性质流量守恒(FlowConservation):ΣF=ΣF当然源和汇不用满足流量守恒最后一个不是很显然的性质是斜对称性(SkewSymmetry):F=-F这其实是完善的网络流理论不可缺少的就好比中学物理里用正负数来定义一维的位移一样百米起点到百米终点的位移是100m的话那么终点到起点的位移就是-100m同样的x向y流了F的流y就向x流了-F的流把图中的每条边上的容量于流量之差计算出，得到参量网

7、络。我们的算法基于这样一个事实：参量网络中任何一条从s到t的有向道路都对应一条原图中的增广路--只要求出该道路中所有残量的最小值d，把对应的所有边上的流量增加d即可，这个过程叫做增广。不难验证，如果增广前的流量满足3个条件，增广后仍满足。显然，只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。“找任意路径”最简单的办法无疑是用DFS，但很容易找出让他很慢的例子。一个稍微好一些的算法是BFS，它足以应对数据不刁钻的网络流题目，这就是Edmonds

8、-Karp算法。在下面的代码中，远点和回电保存在变量s和t中，运行结束后，s-t的净流量保存在变量f中。queueq;memset(flow,0,sizeof(flow));intf=0;while(1){me