最短路问题的Floyd加速算法与优化

doi:10.3778/j.issn.1002-8331.2009.17.012

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (17): 41-43.DOI: 10.3778/j.issn.1002-8331.2009.17.012

最短路问题的Floyd加速算法与优化

张德全,吴果林,刘登峰

桂林航天工业高等专科学校计算机系，广西桂林 541004

收稿日期:2009-02-03 修回日期:2009-03-27 出版日期:2009-06-11 发布日期:2009-06-11
通讯作者: 张德全

Accelerated and optimized method of Floyd algorithm to find out shortest path

ZHANG De-quan,WU Guo-lin,LIU Deng-feng

Department of Computer，Guilin College of Aerospace Technology，Guilin，Guangxi 541004，China

Received:2009-02-03 Revised:2009-03-27 Online:2009-06-11 Published:2009-06-11
Contact: ZHANG De-quan

摘要/Abstract

摘要： Floyd算法是求解网络中任意两点之间最短路的高效算法，文章给出了在不含负回路的网络中Floyd加速算法及优化方法，并构造了求解最短路径的序号矩阵。算法分析和计算实例表明，优化后的Floyd加速算法迭代速度快，计算量大大减少，路径寻找简单、直观。

关键词: 最短路, Floyd 算法, 加速方法, 最短路径

Abstract: Floyd algorithm is the most efficient method to find out the shortest path between any two nodes in the network.This paper illustrates the acceleration and optimization of Floyd algorithm in the network without negative circuit，and establishes serial number matrix to find out the shortest path.The algorithmic analysis and calculation examples show that the amount of calculation reduces greatly after using the accelerated and optimized method of Floyd algorithm and it is simple，intuitive and optimize to find out the path.

Key words: shortest path, Floyd algorithm, accelerated method, path

张德全,吴果林,刘登峰. 最短路问题的Floyd加速算法与优化[J]. 计算机工程与应用, 2009, 45(17): 41-43.

ZHANG De-quan,WU Guo-lin,LIU Deng-feng. Accelerated and optimized method of Floyd algorithm to find out shortest path[J]. Computer Engineering and Applications, 2009, 45(17): 41-43.

[1]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[2]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[3]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[4]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[5]	张林霞，何利文，黄俊. 基于SDN网络的安全设备路由研究[J]. 计算机工程与应用, 2018, 54(4): 103-109.
[6]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[7]	应文杰，徐开，徐少平. 羽毛球机器人机械臂运动轨迹多目标规划[J]. 计算机工程与应用, 2017, 53(3): 258-265.
[8]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[9]	袁亚博，刘羿，吴斌. 改进蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2016, 52(6): 8-12.
[10]	韩建妙，刘业政. 基于遗传算法的超市最短导购路径推荐[J]. 计算机工程与应用, 2016, 52(4): 238-242.
[11]	孟颖翔1，高东怀2，许浩2，许卫中2. 基于最短路径的多子网链路层拓扑发现算法[J]. 计算机工程与应用, 2016, 52(2): 131-134.
[12]	侯晓琴1，胡志华1，高超峰1，罗勋杰2. 自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现[J]. 计算机工程与应用, 2016, 52(12): 31-36.
[13]	吴幸良，涂风华. 采用图模型的个性化标签推荐方法[J]. 计算机工程与应用, 2015, 51(9): 142-146.
[14]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[15]	杜亚娟，郭强. 垃圾中转站最优选址及垃圾最优转运方案研究[J]. 计算机工程与应用, 2015, 51(10): 252-256.

最短路问题的Floyd加速算法与优化

Accelerated and optimized method of Floyd algorithm to find out shortest path

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics