基于矩阵自定义运算的Floyd改进算法

摘要：

解决最短路问题的算法层出不穷，其中最经典的要数Dijkstra算法和Floyd算法。但Dijkstra算法只能得出一对节点间的最短距离，而Floyd算法计算过程十分繁琐。为解决这两种经典算法中的缺陷，提出一种基于矩阵自定义运算的Floyd改进算法。该算法通过自定义矩阵运算得出一个表示两两节点间距离的路权修正矩阵，再用路权修正矩阵与原距离矩阵进行比较，选择两矩阵中对应较小元素组成当前最短路权矩阵，再通过有限次的迭代，从而得到各顶点间的最短路。通过MATLAB仿真，将该算法推广到随机大规模复杂网络中，通过运行时间折线图表明，该算法在节点达到一定数量后运行速度明显优于传统算法，且在稀疏网络中运行效率非常高，说明了该算法的有效性。最后，通过具体应用说明了该算法的实用性。

关键词：最短路问题、Floyd算法、矩阵自定义运算、MATLAB、稀疏网络

所属期刊栏目：26

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61304169

在线出版日期：2016-11-04（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：41-44,49