改进Floyd算法在城市交通网络优化中的应用

Application of Improved Floyd Algorithm in Urban Traffic Network Optimization

指出城市交通道路多节点的特点使得传统Floyd算法在最短路径计算时,过程繁杂且最短路径需要回溯找寻。并提出改进Floyd算法,采用双标号法并去除非必要中间节点路径计算,很大程度上减少了运算次数和时间,提高了算法的时间及空间复杂度,算法效率较高。以某一城市交通道路多节点最短路实际问题为例,运用改进的Floyd算法建立了该问题的数学模型,模型求解和结果分析进一步证明了改进Floyd算法可有效解决赋权交通网络最短路径规划问题。

This paper studies the shortest path planning model for the optimization of the urban traffic network.The multi-nodal characteristic of the urban roads makes the traditional Floyd algorithm complicated in finding the shortest path and necessitates backtrack.Then it improves the Floyd algorithm,using double labeling to sidestep the calculation of unnecessary intermediate nodes and paths,which greatly reduces the quantity and time consumption of the calculation and improves the temporal and spatial complexity and efficiency of the algorithm.Next,in the case of the multi-nodal shortest path problem of the urban road network of a certain city as the example,it uses the improved Floyd algorithm to establish the mathematical model of the problem,solves it and demonstrates with the result that the improved Floyd algorithm can effectively solve the shortest path planning problem of the weighted traffic network.