《网络传输与最大流量算法.刘凌飞[业内资料].doc》由会员分享，可在线阅读，更多相关《网络传输与最大流量算法.刘凌飞[业内资料].doc（11页珍藏版）》请在三一文库上搜索。
1、网络传输与最大流量算法学生：刘凌飞（安庆师范学院数学与计算科学学院） 指导老师：张胜摘要 随着网络事业的发展，网络传输的速度.效率.容量渐渐成为广大用户朋友所关注的问题.本文先向大家介绍网络传输的方式及发展历史，再详细介绍了最大流量的算法问题. 最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径. 目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题.网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设更新以及计算机辅助设计等众多领域.为了方便大家理解，例举了算法的例子来阐述算法的一般流程.关键词 网络传输
2、 光纤 网络流图 最大流量算法 1.网络传输1.1. 网络传输的发展史 随着1946年世界上第一台电子计算机问世后的十多年时间内，由于价格很昂贵，电脑数量极少.早期所谓的计算机网络主要是为了解决之一矛盾而产生的，其形式是将一台计算机经过通信线路与若干终端直接连接，我们也可以把这种方式看做为最简单的局域网的雏形.计算机网络的发展先后经历了远程终端连接.计算机网络阶段（局域网）.计算机网络互联阶段（广域网.Interent）.信息高速公路（高速.多业务.大数据量）四个发展阶段. 2.最大流量及其算法2.1.网络模型.在图示的系统中，我们希望得到从a到z的最大流量.边上标明容量，在a或z之外的两个顶
3、点之间的流向能够任意定向.将这个系统描述为网络模型. b 3 c 5 5 6 2 10 a 6 d 10 e 6 f 4 z 4 5 6 4 6 8 g h 2.1.1.类似的模型还有很多种如;输油管道. b 2 c 3 4 a=码头 5 2 4 z=炼油厂 d 2 e 自来水厂的输水问题. 6 b 4 A 3 2 2 3 c 4 3 d B 2.2.最大流量算法(Ford-Fulkerson Algorithm).也叫做贝尔曼-福特算法，被用于作为一个距离向量路由协议例如RIP, BGP, ISO IDRP, NOVELL IPX的算法.路由器使用这个算法必须维持距离表(其是一个一维数列-“
4、一个向量”)，它告诉距离和发送分组到在网络中的每个节点的最短路径.在距离表中的这个信息是根据邻近节点信息的变化时时更新的.在表中的数据的数量是和网络中所有节点的数量相等的(除了它自己本身).这个表的列代表直接相连的邻节点而行代表所有在网络中的目的地.每个数据包括发送分组到网络中每个目的地的路径和在那个路径输的距离/时间(我们叫做“成本”).在这个算法中测量标准是跳变的数量、延迟时间、流出分组的数量等. =z a= 一致定向的 非一致定向的 路径P在某些含有一致定向边和非一至定向边的从源到汇的通路上也有可能是增加流量.设P是从a到z的一条通路，并设X是P中的一个顶点，它既不是a，也不是z. a
5、. c1 x c2 . z (a) a . c1 x c2 . z (b) a . . c1 x c2 . z (c) a . c1 x c2 . z (d)关联x的变有上图的4中定向.例：求网络的最大流量这个算法求出一个网络的最大流量.每条边的容量是一个非负整数.输入：一个网络，它具有源，汇，容量C，顶点和n输出：最大流量F Proceddure man_flow(a,z,C,v,n) /v的标记是（predecessor（v）,val(v)） /用0流量开始1. for 每条边（i,j）do2.3. while true do4. begin/移去所有标记5. for i:=0 ton d
6、o6. begin7.8. val():=null9. end/ 标记a10. predecessor（a）:=11. val(a):=/U是未考查的有标记的顶点12. U：=a /继续，直到z被标记13. while val（z）=null do14. begin15. if U =then/流量是最大的16. return(F)17. 在U中选择v18. U:=U-v19. ：=val(v)20. for val(w)=null的每条边（v,w）do21. if Fvw0 then29. begin30. predecessor（w）:=v31. val(w):=min,3流为20, 3-
7、5流为10, 5-8流为30，则最小流为10，1-3变为20-10，3-5变为10-10，5-8变为30-10，3-1的流量增加10，5-3的流量增加10，8-5的流量增加10算法流程为maxflow = 0while 有增广路径 maxflow += 最小流 沿增广路径 增广流量增广流量很简单，就是简单地修改图的边的，因此，主要的问题就是如何找增广路径.最简单的办法是直接DFS，在USACO上可以过6个测试点，如果改用邻接表存储图的边，则可以过7个测试点，如果在增广流量的时候把流量为0的路径从邻接表中去除，就可以过8个测试点.要想过下面的4个测试点，就要优化了.瓶颈在DFS上，当然就要用BF
8、S优化，但是BFS的空间复杂度太高，因此采用BFS和DFS结合的方法，先用BFS对每个点标号，然后根据标号进行DFS.如何标号：将源点S标为0，S的邻接点标为1，S的邻接点的未标号的邻接点标为2，.用BFS实现这个很简单如何根据标号进行DFS：只有比该接点的标号多1的邻接点，才递归DFS，否则跳过.附上程序：/*ID: hankjin1LANG: C+TASK: ditch*/#include #include #include using namespace std;/note: TLE of test 8 if no 0 dist path removed/note: TLE of tes
9、t 9int N,M;int ditch201201;int path201201;bool used201;int seq201;int bestseq201;int minV;inline void add(int from, int to, int v) if(ditchfromto=0) pathfrom +pathfrom0 = to; ditchfromto+=v;inline void rm(int from, int to, int v) ditchfromto-=v; if(ditchfromto=0) for(int i=1;i=pathfrom0;i+) if(pathf
10、romi=to) pathfromi=pathfrom pathfrom0 ; break; pathfrom0-; int dfs(int point, int x) seqx=point; usedpoint=true; for(int i=1; i 0) return min(ditchpointj, res); usedpoint=false; return 0;int solve() int total = 0; while(true) fill_n(seq, M+1, 0); fill_n(used, M+1, false); int v = dfs(1, 1);/find max
11、 path if(v = 0) break; total += v; for(int i=1; seqi!=M;i+) rm(seqi, seqi+1, v);/ ditchseqiseqi+1 -= v; add(seqi+1, seqi, v); return total;int main() ifstream fin(ditch.in); ofstream fout(ditch.out); finNM; int a,b,c; for(int i=0;iabc; add(a,b,c); foutsolve()endl; return 0;参考文献【1】左孝凌,离散数学, 上海科学技术文献出
12、版社.1982.【2】Berge;Deo;Lin, 关于网络模型 1968,1985.【3】罗森（）（美），离散数学及其应用（英文第6版），机械工业出版社.【4】苏淳数学奥赛辅导丛书,漫谈数学归纳法M,中国科学技术大学出版社,2009.4.【5】Petri网起源于C.Peter的博士毕业论文Petri.1962.【6】屈婉玲、耿素云、张立昂，离散数学习题解答与学习指导（第2版），清华大学出版社.Network transmission and the maximum flow algorithmStudent: LiuLingFeiGuiding teacher: Zhang ShengAbs
13、tract With the development of the network, the network transmission speed. Efficiency. Capacity gradually become the majority of the concerns of users friends. This article first introduce the network transmission methods and history, and then introduces the problem of maximum flow algorithms. Maxim
14、um flow Problems of graph theory and operations research closely, especially in connection with linear programming, opened up new ways of application of graph theory. At present the theory and application of network flow in the continuous development, there has been a gain of flow, multi-terminal fl
15、ow , multi-commodity flow and network flow decomposition and synthesis of new issues. Application of network flow has been in telecommunications, transport, electricity, project planning, task assignment, design updates, and computer-aided design and other fields. In order to facilitate us to understand, examples Examples of the algorithm to the general process described algorithm.Keywords network transmission fiber-optic network maximum flow algorithm flow diagram. 11思维