基于矩阵运算的最短路优化算法

《基于矩阵运算的最短路优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码：10293密级：硕士学位论文论文题目：基于矩阵运算的最短路优化算法学号1014081707姓名黄奕雯导师赵礼峰学科专业应用数学研究方向数值方法与应用申请学位类别理学硕士论文提交日期二〇一七年三月万方数据MatrixOptimizationAlgorithmBasedonMatrixOperationThesisSubmittedtoNanjingUniversityofPostsandTelecommunicationsfortheDegreeofMasterofScienceByHuangYiwenSupervisor:Prof.ZhaoLifengMarch201

2、7万方数据南京邮电大学学位论文原创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。研究生学号：___________研究生签名：____________日期：____________南京邮电大学学位论文使用授权声明本人授权南京邮电大学可以保留并向

3、国家有关部门或机构送交论文的复印件和电子文档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。涉密学位论文在解密后适用本授权书。研究生签名：____________导师签名：____________日期：_____________万方数据摘要最短路问题作为图论和复杂网络中经典问题，现在在日常生活中，也出现在许许多多方面，比如通信网络，交通网络，旅行商问题中。然而用来求解最短路径的问题的解法也是数见不鲜，

4、其中最典型的要数Dijkstra算法、Ford算法和Floyd算法。然而Dijkstra算法只可求出2个指定节点间的最短距离，Ford算法就只可以求出指定始发点的最短路径，而Floyd算法计算过程相当繁琐。最重要的是，这些算法都是仅仅能解决两节点间的1条最短路。而在实际生活中，我们有时还会因为一些给定的前提条件需要求出两点间次短、渐次短路径。根据以上的不足，本文提出了基于矩阵运算的最短路径优化算法，主要内容如下：1.针对Ford算法进行改进，提出了一种固定始发点的矩阵消去算法，通过寻找从一个固定始发点到其他顶点的路径，其中包括不经过别的顶点，经过一个顶点、经过两个顶点等等逐步迭

5、代，找出从固有始发点到其它的顶点间的最短路。2.给出基于矩阵自定义运算的改良算法。本算法是凭借一种自定义的矩阵运算来求出一个代表每2个节点间距离的路权修正矩阵，然后用路权修正矩阵和原本的距离矩阵来比较，选择2个矩阵中相应较小的元素，组成当前的最短路权矩阵，接着，通过有限次迭代，从而获得各个顶点间的最短路径。并用MATLAB实现，将这种算法运用到随机的大规模复杂网络中去，从运行时间折线图上看出这种算法在节点数到达较大的数量后，算法速度显著提高，在稀疏网络中，该算法的效率特别高，这表明该算法的有效性。最终，经过真实的应用场景表明了这种算法的实用性。3.通过对距离矩阵和路径矩阵的迭代

6、、替换操作，不断从一个节点出发寻找其后继节点，同时通过比较路径长短得到两点间最短路径、次短路径、渐次短路径，并用一个实际例子对该算法的实用价值加以说明。最后，在一个大型网络的实际例子中，通过MATLAB对该算法进行仿真，求得指定顶点间最短、次短、渐次短路径说明该算法能够在复杂大规模随机网络中得到应用。关键词:最短路算法，矩阵消去算法，矩阵自定义运算，稀疏网络，K短路径算法I万方数据AbstractTheshortestpathproblem,asaclassicalproblemingraphtheoryandcomplexnetwork,isalsopresentinlarg

7、enumbersofaspectsindailylife,suchascommunicationnetwork,transportationnetwork,travelingsalesmanproblem.Andthealgorithmtosolvetheshortestpathproblemisalsoemerging.However,Dijkstraalgorithmcanonlygettheshortestdistancebetweenapairofnodes,Fordalgorith