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

• 作者: 赵礼峰 黄奕雯
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最短路问题 Floyd算法 矩阵自定义运算 MATLAB 稀疏网络
• 年，卷（期）: 2016,（10）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 41-44,49
• 页数: 5页
• 分类号: TP301.6
• 字数: 3224字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2016.10.009

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	黄奕雯	南京邮电大学理学院	2	6	2.0	2.0