基于Floyd方法的最短路径算法优化算法

最短路径算法在各领域广泛应用,传统研究方法主要集中在算法应用及单一优化,将两种优化方法集于一体的算法很少.以兰州—北京的铁路运输系统实例,利用Floyd与Dijkstra算法结合、代码优化的方法优化传统Floyd算法.结果表明:优化后的算法在很大程度上减少了运算次数和时间,提高了算法的时间及空间复杂度,算法效率较高.

An Optimized Approach for Shortest Path Determination Based on Floyd Algorithm

The Floyd and Dijkstra shortest path algorithms are classical algorithms which have been widely used in spatial analysis and other areas.Traditional research of the shortest path algorithm focuses on the application of the algorithm and the optimization of one kind of algorithm;the combination of two kinds of optimized methods is rarely seen.This paper attempts to use the method of combining the Floyd algorithm with Dijkstra algorithm and the optimization of the code of traditional Floyd algorithm by taking the Lanzhou—Beijing railway transportation system as an example.The spatial-temporal complexities before and after the optimization of the algorithm,are compared.The experimental results show that the optimized algorithm has greatly reduced the computational count and the operational time.As a result,the algorithm efficiency is improved.