下载文档原格式
网络最大流的算法网络最大流的算法分类：一、Ford-Fulkerson增广路方法1、Ford-Fulkerson标号算法（最简单的实现）分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量，从源点开始扩展，每次选择一个点（必须保证已经扩展到这个点），检查与它连接的所有边，并进行扩展，直到扩展到t。
2、最大容量增广路算法每次找一条容量最大的增广路来增广，找的过程类似Dijkstra，实现起来相当简单。
3、Edmonds-Karp，最短路增广算法的BFS实现每次找一条最短的增广路，BFS是一个可以很方便的实现思想。
4、距离标号算法最短路增广的O(n)寻找实现，使用距离函数d：d[t]=0;d<=d[j]+1若存在(i,j)∈E；只有路径上满足d=d[i+1]+1的增广路才为满足要求的，一开始我们初始化使标号恰好满足要求，之后不断更改标号使其可以使增广继续。
5、Dinic，分层思想对网络分层（按照距t的距离），保留相邻层之间的边，然后运用一次类似于距离标号的方法（其实质是DFS）进行增广。
二、预留与推进算法1、一般性算法随便找个点，要么将他的盈余推出去，要么对他进行重标记，直至无活跃点为止。
2、重标记与前移算法维护一个队列，对一个点不断进行推进与重标记操作，直至其盈余为0，若过程中他没有被重标记过，则可出列，否则加入队头，继续等待检查。
3、最高标号预留与推进算法记录d值，然后优先处理d值较高的，直至没有盈余。
网络最大流的算法实现一、Edmonds-Karp（EK）算法就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)，Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的Dinic 算法都属于此。
SAP 类算法可统一描述如下：Shortest Augmenting Path{ x <-- 0while 在残量网络Gx 中存在增广路s ~> t do{ 找一条最短的增广路径Pdelta <-- min{rij:(i,j) 属于P}沿P 增广delta 大小的流量更新残量网络Gx}return x}在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索(BFS)，E-K 算法就直接来源于此。
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。
对于A中的每一条弧，对应一个数（简记），称之为弧的容量。
通常我们把这样的D叫做网络，记为D=(V,A,C)。
（2）网络流：在弧集A上定义一个非负函数。
是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。
§4 网络最大流问题网络最大流问题是网络的另一个基本问题。
许多系统包含了流量问题。
例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。
许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1 基本概念与定理1．1．网络与流定义14 （1）网络：例1如图7-20是连结某产品产地和销地的交通图。
弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。
现要求制定一个运输方案，使从运到的产品数量最多。
可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件：（1）容量限制条件：对每一条弧，有(7.9)（2）平衡条件：对于中间点：流出量=流入量，即对于每一个i (i≠s,t)，有(7.10)对于出发带点，有(7.11)对于收点，有(7.12)则称为一个可行流，称为这个可行流的流量。
注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧；收点是指只有弧指向，而没有从它的发出去的弧。
最大流问题标号法例题详解最大流问题标号法例题详解本文以一道标号法求解最大流问题的例题胶加以详细讲解，帮助读者了解其原理及运算步骤。
题目如下：给定一个网络结构如下：s (源点) 0----1----2----3----4---- t (汇点)a 25 10 12 15 20其中 s 是源点，t是汇点，aij（i,j=0,1,2,3,4)是每条弧的容量，求整个网络的最大流量。
解：1、设置标号：在最大流问题中，为了求解最大流，最常用的方法是标号法。
首先，要设置各结点标号，因为本题中有5个结点，s源点的标号为0，t汇点标号为4，其他结点即1，2，3依次标号，标号的设定不仅便于求解，而且可以在初始化的时候使用。
2、初始化标号：初始化标号即将各结点初始化为两个空集合{}，即各结点的访问和未访问标号都是空集合，即无访问的结点标号为{}，访问过的结点标号也为{}。
3、依据标号法，从源点(s=0)计算，得出每条弧的剩余容量Cij，具体推导如下：源点0 1 2 3 41 0 25 10 12 152 0 0 10 7 103 0 0 0 8 104 0 0 0 0 20其中：Cij=aij-fij (i,j=0,1,2,3,4)其中，aij 为每条弧的容量，fij 为每条弧的流量，在初始情况下，fij=0，故Cij=aij。
4、找增广路径：从源点s开始，用深度优先搜索法查找从s到t的增广路径，具体步骤如下：设置一个数组P[i]用以记录路径，P[i]表示从s到i节点所经过的上一个结点，先从源点s开始，P[0]=-1，然后查找s出发可以到达的结点，若Cij>0，则有路可达，将P[j]=i（j为s出发可达的结点），接着查找j出发可以到达的结点（该结点未被访问过）若Cjk>0，则有路可达，把P[k]=j，以此类推，直到找到P[t]=-1，即从s到t 的一条增广路径找到，这条增广路径的路径上的容量称为Cmin，它是该增广路径上各结点之间的容量最小值。
最大网速问题的数学模型摘要本题给出了各节点之间的网络流图，需求解它们之间的最大流，即最大网速，为了能有效地解决此问题，我们首先利用求解最大流的标号法对网络图中的可增广链进行逐一分析，并对该链上的流量进行调整，直到该图中没有可增广链后，求得节点1到节点6的最大网速为6兆，然后再通过MATLAB 编程实现对标号法求解的结果进行验证。
最后，又通过提高各节点之间的网速来达到提高从节点1到节点6网速的目的，得出了各链之间增加的具体流量。
即s v 到1v 的容量应增加到263x +，3v 到t v 的容量应增加到22x+，2v 到4v 与4v 到t v 的容量都应增加到72x+。
当然若2023x <<，即03x <<，则s v 到1v 的容量不变。
同理，若032x<<，即06x <<，则2v 到4v 与4v 到t v 的容量也不变。
关键词：网络最大流；可增广链；网络流图；MATLAB ；THE MAXIMUM SPEED ISSUSE MATHEMATICAL MODELABSTRACTThe title gives the network flow graph between nodes, the maximum flow demand solution between them, that is the maximum speed, in order to effectively address this problem, we first use labeling method for solving the maximum flow of the network diagram can be augmented by one chain analysis, and adjust the flow of the chain until after this figure does not augmented chain, and seek the maximum speed node 1 to node 6 is 6 trillion, and then realized through MATLAB programming the results were validated method to solve the label.Finally, and by increasing the speed to achieve between the nodes from node 1 to increase the speed of the object 6, Drawn between the increase in the specific flow chain.In other words, to achieve the purpose of improving x trillion, then s v to 1v the capacity should be increased to 6+2x/3, 3v to t v the capacity should be increased to 2+x/2,2v to4v and 4v to t v the capacity should be increased to7+x/2.Of course, if 0<2x/3<2, that is 0<x<3, s v to1v the capacity to un changed. Similarly, if 0<x/2<3, that is 0<x<6, 2v to4v the capacity is the same and4v to t v.Keywords: network maximum flow; augmenting chain; network flow diagram; MATLAB;目录一问题的提出 (1)二模型假设 (1)三符号说明 (2)四问题的分析 (2)五模型的建立与求解 (2)5.1 模型的建立 (2)5.1.1 可行流 (3)5.1.2 割集 (3)5.1.3 最大流-最小割定理 (4)5.1.4 可增广链推论 (4)5.1.5 寻求最大流的方法 (4)5.1.6 可行流调整算法 (4)5.1.7 最大流的标号算法 (4)5.2 模型的求解 (5)六模型的优化 (13)6.1 网络最大流的算法拓展 (13)6.2 问题的优化求解 (14)模型评价 (16)参考文献 (17)附录 (18)一、问题的提出下图为一网络，节点1到节点2的宽带带宽为6兆，节点1到节点3的宽带带宽为2兆，节点2到节点4的宽带带宽为3兆，…节点4到节点6的宽带带宽为2兆，求节点1到节点6的最大网速。
最优化方法上机实验3求网络最大流及最小费用最大流问题的Ford-Fulkerson标号算法上机时间：2014.01.07实验日期： 2014年1月7日••••••••••••••••••【唯美句子】走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。
懒洋洋的幸福。
顶 3 收藏 2•【唯美句子】一个人踮着脚尖，在窄窄的跑道白线上走，走到很远的地方又走回来。
阳光很好，温暖，柔和。
漫天的安静。
顶7 收藏7•【唯美句子】清风飘然，秋水缓淌。
一丝云起，一片叶落，剔透生命的空灵。
轻轻用手触摸，就点碎了河面的脸。
落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回眸，点亮了生命精彩。
顶11 收藏9•【唯美句子】几只从南方归来的燕子，轻盈的飞来飞去，“几处早莺争暖树，谁家新燕啄春泥，”其乐融融的山林气息，与世无争的世外桃源，让人心旷神怡。
顶0 收藏 2•【唯美句子】流年清浅，岁月轮转，或许是冬天太过漫长，当一夜春风吹开万里柳时，心情也似乎开朗了许多，在一个风轻云淡的早晨，踏着初春的阳光，漫步在碧柳垂青的小河边，看小河的流水因为解开了冰冻而欢快的流淌，清澈见底的的河水，可以数得清河底的鹅软石，偶尔掠过水面的水鸟，让小河荡起一层层的涟漪。
河岸换上绿色的新装，刚刚睡醒的各种各样的花花草草，悄悄的露出了嫩芽，这儿一丛，那儿一簇，好像是交头接耳的议论着些什么，又好象是在偷偷地说着悄悄话。
顶 3 收藏 4•【唯美句子】喜欢海子写的面朝大海春暖花开，不仅仅是因为我喜欢看海，还喜欢诗人笔下的意境，每当夜深人静时，放一曲纯音乐，品一盏茶，在脑海中搜寻诗中的恬淡闲适。
在春暖花开时，身着一身素衣，站在清风拂柳，蝶舞翩跹的百花丛中，轻吹一叶竖笛，放眼碧波万里，海鸥，沙滩，还有扬帆在落日下的古船，在心旷神怡中，做一帘红尘的幽梦。
顶0 收藏 2•【唯美句子】繁华如三千东流水，你只在乎闲云野鹤般的采菊东篱、身心自由，置身置灵魂于旷野，高声吟唱着属于自己的歌，悠悠然永远地成为一个真真正正的淡泊名利、鄙弃功名利禄的隐者。
//标号法求网络最大流量
#include <cstdio>
#include <cmath>
#include <cstring>
#define MAXN 1000 //顶点个数最大值
#define INF 1000000 //无穷大
#define MIN(a,b) ((a)<(b)?(a):(b))
struct ArcType //弧结构
{
int c, f; //容量，流量
};
ArcType Edge[MAXN][MAXN]; //邻接矩阵(每个元素为ArcType类型)
int n, m; //顶点个数和弧数
int flag[MAXN]; //顶点状态：-1－未标号,0－已标号未检查,1－已标号已检查
int prev[MAXN]; //标号的第一个分量：指明标号从哪个顶点得到，以便找出可改进量
int alpha[MAXN]; //标号的第二个分量：可改进量α
int queue[MAXN]; //相当于BFS算法中的队列
int v; //从队列里取出来的队列头元素
int qs, qe; //队列头位置，队列尾位置
int i, j; //循环变量
void ford( )
{
while( 1 ) //标号直至不存在可改进路
{
//标号前对顶点状态数组初始化
memset( flag, 0xff, sizeof(flag) ); //将3个数组各元素初始化为-1
memset( prev, 0xff, sizeof(prev) ); memset( alpha, 0xff, sizeof(alpha) );
flag[0] = 0; prev[0] = 0; alpha[0] = INF; //源点为已标号未检查顶点
qs = qe = 0;
queue[qe] = 0; qe++; //源点(顶点0)入队列
//qs<qe表示队列非空, flag[n-1]==-1表示汇点未标号
while( qs<qe && flag[n-1]==-1 )
{
v = queue[qs]; qs++; //取出队列头顶点
for( i=0; i<n; i++ ) //检查顶点v的正向和反向"邻接"顶点
{
if( flag[i]==-1 ) //顶点i未标号
{
//"正向"且未"满"
if( Edge[v][i].c<INF && Edge[v][i].f < Edge[v][i].c )
{
flag[i] = 0; prev[i] = v; //给顶点i标号(已标号未检查)
alpha[i] = MIN( alpha[v], Edge[v][i].c - Edge[v][i].f );
queue[qe] = i; qe++; //顶点i入队列
}
else if( Edge[i][v].c<INF && Edge[i][v].f > 0 ) //"反向"且有流量
{
flag[i] = 0; prev[i] = -v; //给顶点i标号(已标号未检查)
alpha[i] = MIN( alpha[v], Edge[i][v].f );
queue[qe] = i; qe++; //顶点i入队列
}
}
}
flag[v] = 1; //顶点v已标号已检查
}//end of while( qs<qe && flag[n-1]==-1 )
//当汇点没有获得标号，或者汇点的调整量为0，应该退出while循环
if( flag[n-1]==-1 || alpha[n-1]==0 ) break;
//当汇点有标号时,应该进行调整了
int k1 = n-1, k2 = abs( prev[k1] );
int a = alpha[n-1]; //可改进量
while( 1 )
{
if( Edge[k2][k1].f<INF ) //正向
Edge[k2][k1].f = Edge[k2][k1].f + a;
else Edge[k1][k2].f = Edge[k1][k2].f - a; //反向
if( k2==0 ) break; //调整一直到源点v0
k1 = k2; k2 = abs( prev[k2] );
}//end of while( 1 )
}//end of while( 1 )
//输出各条弧及其流量，以及求得的最大流量
int maxFlow = 0;
for( i=0; i<n; i++ )
{
for( j=0; j<n; j++ )
{
if( i==0 && Edge[i][j].f<INF ) //求源点流出量，即最大流
maxFlow += Edge[i][j].f;
if( Edge[i][j].f<INF ) printf( "%d->%d : %d\n", i, j, Edge[i][j].f );
}
}
printf( "maxFlow : %d\n", maxFlow );
}
void main( )
{
int u, v, c, f; //弧的起点、终点、容量、流量
scanf( "%d%d", &n, &m ); //读入顶点个数n和弧数m
for( i=0; i<n; i++ ) //初始化邻接矩阵中各元素
{
for( j=0; j<n; j++ ) Edge[i][j].c = Edge[i][j].f = INF; //INF表示没有直接边连接
}
for( i=0; i<m; i++ ) //读入每条弧
{
scanf( "%d%d%d%d", &u, &v, &c, &f ); //读入边的起点和终点
Edge[u][v].c = c; Edge[u][v].f = f; //构造邻接矩阵
}
ford( ); //标号法求网络最大流
}
代码来自。
