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

An Improved Shortest Path Algorithm Based on Vertex Degree Search

作　　者：张云丽[1] 莫辉辉[1] 邓连波[1] 

机构地区：[1]中南大学交通运输工程学院,湖南长沙410075

出　　处：《交通运输系统工程与信息》2004年第2期56-58,共3页Journal of Transportation Systems Engineering and Information Technology

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

关 键 词：计算机应用 最短径路 DIJKSTRA算法 度搜索 复杂度 

分 类 号：U495[交通运输工程—交通运输规划与管理]