A Kind of Shortest Path Algorithm Based on Dijkstra
Yan Li · Neimenggu Shi-da xuebao. Zhexue shehui kexue hanwen ban · 2012
Shortest path algorithm has important practical value in engineering practice and Dijkstra algorithm is a classical algorithm for solving the shortest path.Dijkstra algorithm is the theoretical basis for many practical works to solve the shortest path problem,but many of the restrictions involved in the actual project,therefore,there must be the algorithm improvement and optimization.On the basis of analyzing the classical Dijkstra algorithm,the paper discusses an improved algorithm of Dijkstra algorithm.By using Map which is stored in the algorithm to the adjacency table,it can avoid the limitations of the adjacency matrix in the project;Moreover,in the calculation of the shortest path,using a combination of the priority queue with reverse N-tree.In order to down grade the priority queue to improve the Dijkstra algorithm.The paper puts forwards the methods and processes to improve the shape Dijkstra algorithm,and analyzes the complexity of the algorithm and do some detailed testing and results analysis.