网络最短路径问题的研究与应用.pdf

《网络最短路径问题的研究与应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、■■．ＩＩ＇—．ｉＸ：＇《？＇Ｉ＇？－；单位代码：１０巧３密级．；ＴＩ．；｜１．｜ＩＩＩ＇＇＇一．心？．＾Ｖ孰—／挺．’？．－＊、，？？．？？；．’＾’Ａ＾‘．－Ｖ．讀＾雀：遗４１＊｜苗｜谭＇硕女＃您化Ａ苗．、．ｔ’＇．＇＇？．：．．瓶．績樂．．祕緯；ｆ一．＊？－＂．‘？？’．？．哪？？？＇．—．ｒ；主户．换，、、一、／一…＾．、＇：．．書：恥．．Ｖ＇户、．共７Ｖ，／冷＊乂’＇Ｉ赵；＇＇＇、．论文题目．：网络最短路径问题的研究与

2、应用＇；‘戶：，识学号Ｑ１２Ｑ８１７１３Ｌ＇？－＜；姓名Ｖ，：梁，娟：导师赵礼峰亦，；‘’＇应用数学．＃ｒ学科专业，巧、；＇‘ｖ．如．硏究方向数值方法与应用ｙ义：＊＂＊＊＊－＊？＇■Ｖ＾？巧’．．．串请学位类别次■六ｉ義一一＾．五年二月．．零日期＾Ｖ．．论文提交、卢＇１乂＂：．．、，１１、一轉？巧纖節货閑？．？？刊．．心－．．黄－．．六巧：．巧心ｒ媒繁靈１；南京邮电大学学位论文原创性声明尽本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的

3、研究成果。我所知，除了文中特别加标注和致谢的地方外，论文中不包含其他人己经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。一与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。一本人学位论文及渉及相关资料若有不实，愿意承担切相关的法Ｗ律责任。矣年．／之研充生签名；．裴日期；刘南京邮电大学学位论文使用授权声明本人授权南京邮电大学可从保留并向国家有关部口或化构送交论文的复印件和电子文可培；允许论文被查阅和借阅；可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索；！＾采用

4、影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研巧生院办理。涉密学位论文在解密后适用本授权书。研究生签名；讓导师签名日期：ＷｌＳ．中，种ResearchandApplicationofNetworkShortestPathProblemThesisSubmittedtoNanjingUniversityofPostsandTelecommunicationsfortheDegreeofMasterofScienceByLiangJuanSupervisor:Prof.ZhaoLi

5、fengMarch2015摘要最短路径问题是图论和网络优化理论研究的主要问题，用于求解网络中任意两点之间的最短路径。随着科技的发展，最短路径问题在计算机科学、地理信息科学、通信与军事运筹学等领域发挥越来越大的作用。因此，研究最短路径问题意义重大。首先，通过分析Bellman-Ford算法，针对其求解最短路长重复计算量大，寻找最短路径繁琐的问题，本文提出Ford算法的改进算法。改进算法通过引入路权数组有效降低了算法的时间复杂度，同时借助前点标号数组增强了寻路直观性。编写MATLAB程序，并在大型随机网络中仿真实验，结果显示Ford算法的改进算法更为有效。其次，对Floyd算法进

6、行深入研究，通过引进迭代矩阵和下标标注法对其进行改进。Floyd改进算法提高了计算最短路长的效率，简化了寻找最短路径的步骤。给出算法复杂度、可行性分析和具体实例，并用Floyd改进算法与原算法计算大型网络最短路，理论分析和仿真结果都说明了改进算法的准确性和高效性。再次，本文提出用三个值标记一个节点的拓扑排序法的修正算法，修正算法通过增加前点标号改善了拓扑排序法求解最短路径繁琐的问题，通过只更新与出弧相连节点的标记，简化了计算量，提高了计算效率。最后，简单介绍最短路径问题在通信中的应用及其推广应用。关键词:最短路径，Bellman-Ford算法，Floyd算法，改进算法，随机网

7、络IAbstractTheshortestpathproblemisthemainproblemofgraphtheoryandthetheoryofnetworkoptimization,anditismainlyusedtofindtheshortestpathbetweenanytwopointsinthenetwork.Withthedevelopmentofscienceandtechnology,theshortestpathproblemplaysmoreandmoreimportantr