基于矩阵运算K短路径算法

• 作者: 赵礼峰 黄奕雯
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 次短路径 渐次短路径 距离矩阵 路径矩阵
• 年，卷（期）: 2017,（4）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 98-103
• 页数: 6页
• 分类号: TP301.6
• 字数: 4534字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2017.04.022

摘要

最短路问题是复杂网络中的经典问题,其求解算法层出不穷,各有优缺点.经典的算法包括Dijkstra算法、Ford算法和Floyd算法等,只能求解两节点间的一条最短路径.在实际生活中,还需要在大型网络中限定一些前提条件求解两点间次短、渐次短的路径问题.为此,提出了一种对距离矩阵和路径矩阵的迭代、替换算法,即从一个节点出发寻找其后继节点,同时通过比较路径长短得到两点间最短路径、次短路径和渐次短路径,并不断重复、替换.为验证所提算法的有效性,以一个大型网络的应用作为实例,应用Matlab对所提算法进行了仿真实验验证.仿真结果表明,所提算法能够在复杂大规模随机网络中满足求解指定顶点间最短、次短和渐次短路径的需要,具有较好的有效性和适用性.

作者信息

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