Improved algorithm about searching for the shortest path over the traffic network

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (14): 220-222.

• 工程与应用 • Previous Articles Next Articles

Improved algorithm about searching for the shortest path over the traffic network

Received:2006-06-06 Revised:1900-01-01 Online:2007-05-10 Published:2007-05-10

基于交通网络最短路径搜索的改进算法

刘韵何建农

福州大学数学与计算机科学学院

通讯作者: 刘韵

Abstract

Abstract: In this paper a new algorithm about searching for the shortest path in a weight graph is introduced. Taking the traffic network into consideration, the algorithm is based on the edges searching. This algorithm is better than the Floyd algorithm in average time complexity.

Key words: the shortest path, Floyd, EBSP, EBSP*

摘要： 对全源最短路径搜索算法进行了深入的研究分析，并结合国内城市道路交通的实际情况，提出了基于边序列最短路径搜索算法的一种改进算法——EBSP*算法。该算法在平均时间复杂度上比传统的Floyd最短路径搜索算法有较大的提高。

关键词: 最短路径, Floyd, EBSP, EBSP*

刘韵何建农. 基于交通网络最短路径搜索的改进算法[J]. 计算机工程与应用, 2007, 43(14): 220-222.

[1]	ZHANG Linxia, HE Liwen, HUANG Jun. Route of security device research based on SDN Network [J]. Computer Engineering and Applications, 2018, 54(4): 103-109.
[2]	LI Chaoyan1, PEI Lintao2. Difference of multi-thread parallel Floyd algorithm with macro parameter and global variable [J]. Computer Engineering and Applications, 2014, 50(16): 45-47.
[3]	XIE Ying1, HAN Yanglong1, ZHAO Gang2, YU Fucai1, HU Guangmin1. Geographic routing protocol for pseudo three-dimensional wireless sensor networks [J]. Computer Engineering and Applications, 2013, 49(22): 63-67.
[4]	LI Wei¹，GUO Qiang¹，CAO Hua². Optimal matching problem with constraint of success ratio [J]. Computer Engineering and Applications, 2011, 47(4): 33-35.
[5]	YANG Chunde¹，DENG Chao². Improved algorithm of DVBMT problem [J]. Computer Engineering and Applications, 2011, 47(3): 84-86.
[6]	LU Zhao，SHI Jun. Design and implementation of parallel shortest path search algorithm [J]. Computer Engineering and Applications, 2010, 46(3): 69-71.
[7]	FAN Chang-sheng¹，GUO Qiang¹，YUE Ai-feng². Optimal path algorithm for network with direction-prohibited routes among some nodes [J]. Computer Engineering and Applications, 2009, 45(23): 59-62.
[8]	ZHANG De-quan,WU Guo-lin,LIU Deng-feng. Accelerated and optimized method of Floyd algorithm to find out shortest path [J]. Computer Engineering and Applications, 2009, 45(17): 41-43.
[9]	LI Yan,GUO Qiang. Algorithm for uncertainty assignment problem [J]. Computer Engineering and Applications, 2009, 45(15): 61-63.
[10]	. Multiple depot multi-logistics center distribution problem [J]. Computer Engineering and Applications, 2007, 43(8期): 202-204.
[11]	GUO qiang. Iterative algorithm of total assignment problem on persons less than jobs [J]. Computer Engineering and Applications, 2007, 43(24): 91-93.

Improved algorithm about searching for the shortest path over the traffic network

基于交通网络最短路径搜索的改进算法

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics