摘要
Floyd算法能胜任求解任意两节点之间最短路径任务,但随着节点数的增加,冗余计算也随之增加,文中总结分析了现有研究成果,对Floyd算法进行改进,去除非必要中间节点路径计算,降低计算量,有效提高Floyd算法计算效率。城市交通道路多节点的特点使得Floyd算法在最短路径规划过程中计算繁杂,运用改进Floyd算法进行交通节点间最短路径规划,改进算法将原计算复杂度由O(n^3)降低为O(1/2n^3),有效降低了计算复杂度,提高计算效率,在不包含负回路城市交通网络中完成最短路径规划。
The Floyd algorithm is suited for solving the shortest path between any two nodes of the problem, but with the increase of the number of nodes, its redundant calculation increase. An improved Floyd algorithm is proposed to reduce the amount of calculation and improving the efficiency of calculation. The proposed Floyd algorithm is apply to the shortest path planning in the urban traffic network. The computation complexity of the improved algorithm is decreased by O（n^3 ） to O（1/2n^3） .
出处
《电子科技》
2017年第7期17-20,共4页
Electronic Science and Technology
基金
国家自然科学基金(61602489)
