一种改进的Floyd算法
|
摘要
Floyd算法是解决最短路径问题的一种有效方法,算法简单,边权值可正可负,同时也被用于计算有向图的传递闭包。但存在着时间复杂度高等问题,不适合计算大量的数据。从搜索方向和数据存储的角度,对其进行了改进。理论分析和实验结果表明,改进的算法在运行时间和程序占用内存方面均优于传统的Floyd算法。
Floyd algorithm is an effective method to solve shortest path problem. The algorithm is simple and the edge value can be negative,and it is also used to calculate the transitive closure of the directed graph. But there are some shortages,such as high time complexity,which is not suitable for calculating a large number of data.Starting from the search direction and the way of data storage,the Floyd algorithm is modified. Theoretical analysis and experimental results show that the modified algorithm is superior to the traditional Floyd algorithm in terms of running time and program memory occupancy.
Floyd algorithm is an effective method to solve shortest path problem. The algorithm is simple and the edge value can be negative,and it is also used to calculate the transitive closure of the directed graph. But there are some shortages,such as high time complexity,which is not suitable for calculating a large number of data.Starting from the search direction and the way of data storage,the Floyd algorithm is modified. Theoretical analysis and experimental results show that the modified algorithm is superior to the traditional Floyd algorithm in terms of running time and program memory occupancy.
引文
鲍培明.2000,.Dijkstra算法在动态权值系统中的应用[J].计算机工程,26(4):11-12.
陈华容,张崇富.2006.Bellman-Ford算法的改进研究[J].电子科技大学学报,35(2):211-213.
崔焕庆,王英龙.2011.求解多段图问题的并行动态规划算法[J].计算机应用与软件,28(12):32-34.
郝自军,何尚录.2008.最短路问题的Floyd算法的若干讨论[J].重庆理工大学学报,22(5):156-159.
乐阳,龚健雅.1999.Dijkstra最短路径算法的一种高效率实现[J].武汉大学学报:信息科学版,24(3):209-212.
李洪波,王茂波.2006.Floyd最短路径算法的动态优化[J].计算机工程与应用,42(34):60-63.
彭强.2010.基于并行Boost图库的单源最短路径并行算法的研究[D].广州:华南理工大学.
夏正冬,卜天明,张居阳.2014.SPFA算法的分析及改进[J].计算机科学,41(6):180-184.
朱立,夏洪,钱敏.2010.基于GIS的无线网络覆盖模拟建模[J].东华理工大学学报:自然科学版,33(4):384-388.
左秀峰,沈万杰.2017.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,44(5):232-234.
Dijkstra E W.1959.A note on two problems in connexion with graphs[J].Numerische Mathematik,1(1):269-271.
Floyd R W.1962.Algorithm 97:Shortest path[J].Comm Acm,5(6):345.
Nickolls J,Ian B,Michael G,et al.2008.Scalable Parallel Programming with CUDA[J].Queue,6(2):1-9.
陈华容,张崇富.2006.Bellman-Ford算法的改进研究[J].电子科技大学学报,35(2):211-213.
崔焕庆,王英龙.2011.求解多段图问题的并行动态规划算法[J].计算机应用与软件,28(12):32-34.
郝自军,何尚录.2008.最短路问题的Floyd算法的若干讨论[J].重庆理工大学学报,22(5):156-159.
乐阳,龚健雅.1999.Dijkstra最短路径算法的一种高效率实现[J].武汉大学学报:信息科学版,24(3):209-212.
李洪波,王茂波.2006.Floyd最短路径算法的动态优化[J].计算机工程与应用,42(34):60-63.
彭强.2010.基于并行Boost图库的单源最短路径并行算法的研究[D].广州:华南理工大学.
夏正冬,卜天明,张居阳.2014.SPFA算法的分析及改进[J].计算机科学,41(6):180-184.
朱立,夏洪,钱敏.2010.基于GIS的无线网络覆盖模拟建模[J].东华理工大学学报:自然科学版,33(4):384-388.
左秀峰,沈万杰.2017.基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,44(5):232-234.
Dijkstra E W.1959.A note on two problems in connexion with graphs[J].Numerische Mathematik,1(1):269-271.
Floyd R W.1962.Algorithm 97:Shortest path[J].Comm Acm,5(6):345.
Nickolls J,Ian B,Michael G,et al.2008.Scalable Parallel Programming with CUDA[J].Queue,6(2):1-9.