Research And Application Of Shortest Path Algorithm Based On Urban Road Network

Nowadays,the city has expanded,the number of cars has increased,and the traffic congestion problem is one of the important problems that China needs to solve.The key technology to solve the traffic jam problem in urban road network lies in the study of the shortest path.Therefore,it is of great significance to study the shortest path algorithm based on urban road network.This paper focuses on the Dijkstra algorithm for solving the shortest path of urban road network and the Yen algorithm for solving the shortest path of K.The main work is as follows:(1)In the storage of urban road network graphs,there is a problem of large data redundancy when the adjacent matrix stores sparse graphs.This paper proposes to store the urban road network graph with adjacency table data structure and reduce the spatial complexity of Dijkstra algorithm.(2)Dijkstra algorithm is broad searching,time-consuming and many nodes ergodic in the aspect of optimization of search scope.This paper makes an in-depth analysis of the problems of elliptic search algorithm and rectangular search algorithm to optimize Dijkstra algorithm,and gives the search range and the area formula of the two algorithms according to the characteristics of the road network.And it is proved that using the rectangular algorithm to optimize Dijkstra algorithm is feasible and efficient through the experiments.(3)The Yen algorithm is improved for solving the problem that the shortest path calculation is more complex and the time complexity is high.By introducing the evaluation function,only the node with the lowest value is chosen as the final deviation node,and the complexity of the algorithm is reduced.Based on the experiment,two algorithms are compared and analyzed from the algorithm path finding time,the path length required by the algorithm and the number of candidate paths generated in the path finding process,and the validity of the algorithm is verified.(4)Based on unity3 d and 3dsMax,the virtual city road network routing system is designed and implemented by using the model optimization technology.The rectangular search algorithm and the heuristic search improved Yen algorithm are applied to the virtual urban road network routing system and verified The efficiency and feasibility of the proposed method in this paper,have reached the expected effect of path finding.