网络流算法研究和应用分析.pdf

Research andApplied work Flow Algorithm ThesisSubmitted toNanjing University of Posts and munications for the Degree of Master of Science By Dong Fang Supervisor: Prof. ZhaoLifeng February2014 万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实,愿意承担一切相关的法律责任。南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档;允许论文被查阅和借阅;可以将学位论文的全部或部分内容编入有关数据库进行检索;可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布(包括刊登) 授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名:_____________ 日期:____________ 研究生签名:____________导师签名:____________ 日期:_____________ 万方数据 I 摘要网络流问题是网络最优化问题中至关重要的部分,它在生活和各个科学领域的应用也愈加广泛。随着计算机科学技术的进步和人们对其深入的研究,形成了较完善的理论体系,从而建立了一系列有效算法。本文针对增广链的选取具有不稳定性而得不到理想的最大流问题进行改进,并对最大流问题的应用进行研究。主要创新工作是: (1)介绍了几种求最大流问题的经典算法,并通过实例对这些经典算法进行优缺点和局限性的分析,广泛吸取标号算法的最新成果并引进断链的基本概念,提出了一种基于断链求解网络最大流的新标号算法。同时通过实例和仿真实验进行了验证,验证了该算法具有可行性与高效性。(2)针对现有算法没有给出明确的选择增广链路径的方法,造成计算复杂等问题,于是对原有算法的一些缺点进行改进,又应用分层、度差、容差等概念,提出了一种基于度差求解网络图最大流的新算法。通过实例和仿真实验验证该算法具有明显的稳定性与有效性。(3)由于上述提出的改进的新标号算法,它不但可以解决最大流问题同时也为求解最短路问题提供了一种方法,于是提出了一种基于新标号算法求解小规模网络最短路问题的算法。通过实例验证该算法的简单可行性。(4)给出最大流算法在通信网络中的应用以及它的推广应用。关键词:最大流,增广链,最短路,标号算法,剩余容量,顶点度,网络编码万方数据 II Abstract The maximum flow problem plays an importantrole in work optimization is widely applied in life and each field of the booming development of computer technology,people research inmaximum flow problemdeeply,scholars set up muchperfect theoretical systemand series of effective algorithms. Due totheimproper selection order of augmented chaincouldnot obtain the idealmaximum flowand do some researchon the maximum flow problem, the paperdoes the followingsomemain innovation works: Firstly, the paper introduces some classicalgorithm, then it analyzestheiradvantages and disadvantages,verifiestheirslimitationsby examples. In addition, using the concept of disconnectedchainsandabsor