An Improved Shortest Path Algorithm Based on Vertex Degree Search
Lianbo Deng · Communication and Transportati0n Systems Engineering and Information · 2004
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) .