计算机技术与发展2016，Vol.26Issue(10)：41-44,49,5.DOI:10.3969/j.issn.1673-629X.2016.10.009
基于矩阵自定义运算的Floyd改进算法
Improved Floyd Algorithm Based on Customized Matrix Operations
摘要
Abstract
The algorithm to solve the shortest path problem is endless,and the algorithm of Dijkstra and Floyd is the most typical. Howev-er,the Dijkstra algorithm can only get the shortest distance between a pair of nodes,and Floyd algorithm is very cumbersome. For solving their defects in two classical algorithms,an improved Floyd algorithm is proposed based on matrix custom operation. It obtains a modified matrix between two nodes by using a customized matrix calculation,and then compares the modified matrix with the original distance ma-trix,selecting the smaller matrix elements for composition of the shortest path weight matrix. Through finite iteration,the shortest path is obtained between each vertex. By the MATLAB simulation,the algorithm is extended to stochastic large-scale complex networks. The running time line chart shows that this algorithm runs faster than traditional algorithm after a certain number of nodes,and in sparse net-work,the efficiency is particularly high,which shows the its effectiveness. Finally,by using the specific application,the feasibility of the algorithm is verified.关键词
最短路问题/Floyd算法/矩阵自定义运算/MATLAB/稀疏网络Key words
shortest path problem/Floyd algorithm/matrix custom operations/MATLAB/sparse network分类
信息技术与安全科学引用本文复制引用
赵礼峰,黄奕雯..基于矩阵自定义运算的Floyd改进算法[J].计算机技术与发展,2016,26(10):41-44,49,5.基金项目
国家自然科学基金资助项目(61304169) （61304169）
