几种网络最大流算法比较

目标；三是从约束函数的角度出发，研究需求量和供给量在区间变动的不确定型的运输问题、时间窗口运输问题等。 1.2选题意义

网络流问题主要研究的是网络最优化问题,在工程及科学等领域均有重要作用。其主要内容包括最短路、最大流及最小费用流等问题,随着信息技术的发展人们建立了较为完善的理论,提出了一系列相应的算法,取得了令人瞩目的成绩。

而且我们在日常生活中时常遇到这样一些图，如旅游线路图、交通图、管道系统图等。这些图在优化理论中就是所谓的对所对应的实际情况进行的抽象和概括，用图来表示我们研究的对象以及对象之间的联系是很方便、直观的。比如网络通信、旅游管理、金融系统、交通运输等问题都可以用网络图来表示。

最大流问题应用极其广泛，很多生活中的问题都可以转化为最大流问题，其难点是从实际生活中抽象出最大流模型，即转化问题，且实践性较强，通过实例分析，更有利于对最大流问题的了解与应用。

2.预备知识

2.1图论

所谓的图论，顾名思义就是研究图的理论。图论中的图是由一些实际问题经过抽象而得到的，由点和点与点之间的线构成，它能反映一些对象之间的关系。图形中的点表示一些对象(如通讯站、选手、工序等)，两点之间的有向或者无向的线表示对象之间有某种特定的关系(如胜负关系、先后关系、连接关系、传递关系等)[6]。

电路网络、物质结构、交通运输、城市规划、物资调配、信息传递等都可以用点和线连接的图进行模拟。而这里研究的图和平面几何中的图有些不一样，这里只关心图中有几个点，点与点之间有没有线，至于连线的方式是曲线还是直线点与点的相对位置怎样都是无关紧要的[7]。

下面介绍一些网络最大流问题会用到的相关的定义：

定义1：由点和边构成的图为无向图，记为G?(V,E)；由点和弧构成的图为有向图，记为D?(V,A).

定义2：在无向图G中，若存在一个点边交错序列(vi1,ei1,vi2,ei2,?vik?1,eik?1,vik)，满足

eit?[vit,vit?1](t?1,2,?k?1)，则称之为一条联结vi1和vik的链，记为(vi1,vi2,?,vik),若vi1?vik，则称之为圈。

3

定义3：在有向图D中，若存在一个点弧交错序列(vi1,ai1,vi2,ai2,?vik?1,aik?1)，弧

ait的始点为vit，终点为vit?1，记为ait?(vit,vit?1)，则称这条点弧的交错序列为从vi1到vik的一条路，记为(vi1,vi2,?,vik)。若路的第一点和最后一点相同，则称之为回路。链与路中的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。 定义4：如果对于一个有向图D的每一条弧，相应有一个权数cij，称这样的图为网络,记为D?(V,A,C) [6] 。

一般在网络图中，每条弧的权代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络。 2.2网络最大流算法

要想知道什么是网络最大流算法就必须先要知道什么是网络最大流问题，那什么是网络最大流问题呢？所谓网络最大流问题就是，给了一个带收发点的容量网络N，求N上使达到最大的可行流(称这样的可行流为最大流)。 我们先将一个复杂的网络问题进行转化，使之成为典型的网络问题，再对相应的限制条件进行抽象化、理论化，在此基础上，进行分析和研究，找出解决办法。最大流问题已经有40多年的研究历史，这短时间内，人们建立了最大流问题较为完善的理论，同时开发了大量的算法，如Ford-Fulkerson算法，Edmonds-Karp修正算法，Dinic算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的研究。

所谓的网络最大流问题就是在一个有向连通的图中，指定一个点为发点，另外一个为收点，其他的都称为中间点，在所有的点都能够承受的情况下，通过这个网络图的最大的可行流，即为发点到收点的最大的可行流。[8]。

众所周知，在1955年 ，T.E.哈里斯在研究铁路的最大通量时提出在一个给定的网络上来寻求两点间最大运输量的问题。而在1956年，L.R. 福特和 D.R. 富尔克森等人就给出了这类问题的解决算法，从而建立了网络流理论。所谓网络或者容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是顶点集，E是有向边集，C是弧上的容量。除此外顶点集中还包括一个起点和一个终点。网络上的流就是从起点流向终点的可行流，这就是定义在网络上的非负函数。但是它一方面要受到容量的限制；而另一方面，除去起点和终点之外，所有中途点都要求保持流入量和流出量的平衡。如果把一个图看作公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。如果把一个图看作输油管道网 ， v1 表示发送点，v6表示接

4

收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。

3.几种网络最大流算法的分析与比较

本文所研究的几种算法在众多求解网络最大流算法中是比较常用的，也是网络最大流算法中比较典型的例子，能够代表相当一部分的网络最大流算法。下面就来分析一下具体的算法。 3.1 Ford-Fulkerson算法 3.1.1算法介绍与分析

Ford-Fulkerson算法是一个找最大流f的算法。它是由Fulkerson和Ford在1957年最早提出的[9]，基本思想是从任意一个可行流出发，寻找—条增广路径，并且在这条增广路径上增加流量，于是便得到一个新的可行流，然后再在这新的可行流上找一条新的增广路径，然后再增加流量……，接着继续这个过程，一直到找不到新的增广路径为止。

用Ford-Fulkerson求最大流问题的时候，一个点只有以下三种状态：1、标号已检查；2、标号未检查；3、未标号。

Ford-Fulkerson算法总共分为两个过程：一是标号过程：通过标号找到一条增广路径；二是增广过程：沿着增广路径来增加网络流的流量[10]。下面我们来分析一下Ford-Fulkerson算法的复杂度，时间复杂度为O(m*n*u)。其中m为弧的数目，n是迭代次数，u为弧上容量最大上界，是伪多项式的算法。邻接表来表示图，空间复杂度为O(m+n)。而Ford-Fulkerson方法的实际运行效率也取决于如何确定增广路径。如果路径选取不好，可能每次增加的流就非常少，而且算法运行时间也会非常长，甚至是无法终止，所以对增广路径寻找方法的不同导致求最大流算法的不同。

Ford-Fulkerson是一种迭代方法，它采用的是深度优先策略。 3.1.2算法实现

下面我们来将Ford-Fulkerson算法具体实现一下:

#include #include using namespace std; const int maxN=201;

5

static int edge[maxN][maxN]; bool visited[maxN]; int father[maxN]; int N, M; int ans;

void Ford_Fulkerson( ) { while(1) {

queue q;

memset(visited, 0, sizeof(visited)); memset(father, -1, sizeof(father));

int now; visited[0] = true; q.push(0); while(!q.empty())

{ now = q.front(); q.pop(); if(now == M-1) break; for(int i=0; i

if(edge[now][i] && !visited[i])

{ father[i] = now; visited[i] = true; q.push(i); }

} }

if(!visited[M-1]) break; int u, min = 0xFFFF; for(u=M-1; u; u=father[u])

{ if(edge[father[u]][u] < min) min = edge[father[u]][u]; }

for(u=M-1; u; u=father[u])

{ edge[father[u]][u] -= min; edge[u][father[u]] += min;

6