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


刘韵 何建农   

  1. 福州大学数学与计算机科学学院
  • 通讯作者: 刘韵

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*