交通运输系统工程与信息

交通运输系统工程与信息 ›› 2004, Vol. 4 ›› Issue (2): 56-58 .

• 系统工程理论与方法 • 上一篇    下一篇

基于“度搜索”的最短径路算法

张云丽，莫辉辉，邓连波   

  1. 中南大学交通运输工程学院，湖南长沙410075
  • 收稿日期:2003-09-22 修回日期:1900-01-01 出版日期:2004-05-01 发布日期:2004-05-01

An Improved Shortest Path Algorithm Based on Vertex Degree Search

ZHANG Yun-li，MO Hui-hui，DENG Lian-bo   

  1. School of Traffic and Transportation Engineering, Central South University, Changsha，410075，China
  • Received:2003-09-22 Revised:1900-01-01 Online:2004-05-01 Published:2004-05-01

PDF

摘要： 最短径路是网络优化中的一个经典问题，Dijkstra算法被公认为是一种十分有效的最短径路的搜索求解算法.本文在研究网络一般结构特点的基础上，发现传统Dijkstra算法在每次迭代过程中都需要搜索所有节点的这一缺陷，通过向搜索节点中引入“度”的信息，提出了基于“度搜索”的改进算法，并根据网络的特点，给出了有向网络和无向网络两种情况下存在“度”差异的算法设计方法;算法的整体结构与Dijkstra保持T一致性，没有算法结构的突变，因而通过修改原有Dijkstra程序和重新设计“度搜索”程序都十分容易实现.该算法提高了最短径路的搜索效率，特别是对稀疏网络，算法效率更为明显，其复杂度小于O(IV12).

关键词: 计算机应用, 最短径路, Dijkstra算法, 度搜索

Abstract:

The shortest path problem is a classical problem of network optimization. Its practical application and theoretic research is valuable. In most practical application, the shortest path problem has constrains and it is NP-complete，so to find out a rapid and effective algorithm for original SP will put good‘ idea for practical SP problem solution. Dijkstra algorithm is regarded as a more effective algorithm for searching shortest path. Many algorithms are improvements for it. The main change includes network transform and data structure. Through research, we find out a fault that the Dijksta algorithm searches all vertexes in each iteration cycle. Different from the traditional vertex degree，it shows the edge or arc number when searched each time. Based on its theory, an improved Vertex-Degree-Search algorithm is put forword, and tow algorithms due to the direct network and indirect network are developed. The algorithm design structure is the same as Dijkstra’s，so it is so convenient to modify the Dijkstra program or to develop new program. The algorithm improves the search efficiency of shortest path. The efficiency is more obvious，especially for sparse network. Its complexity is less than O(1V12).

Key words: shortest path, dijkstra algorithm, vertex degree search