基于改进Floyd算法的城市交通网络最短路径规划

摘要

Floyd算法能胜任求解任意两节点之间最短路径任务,但随着节点数的增加,冗余计算也随之增加,文中总结分析了现有研究成果,对Floyd算法进行改进,去除非必要中间节点路径计算,降低计算量,有效提高Floyd算法计算效率.城市交通道路多节点的特点使得Floyd算法在最短路径规划过程中计算繁杂,运用改进Floyd算法进行交通节点间最短路径规划,改进算法将原计算复杂度由O(n3)降低为O((1/2)3),有效降低了计算复杂度,提高计算效率,在不包含负回路城市交通网络中完成最短路径规划.