The Optimization And Realization Of The Shortest Path Algorithm Within Actual Road Network

The research of intelligent transportation system emerged as the times require, to fix the congestion and pollution better, which are caused by the rapid rise of the cars as the urban economy has surged. The traffic guidance system is an important subsystem of intelligent transportation system, which has been studied by industry experts and scholars extensively. and its key point is the shortest path algorithm. The Dijkstra algorithm is the most widely used single source shortest path algorithm in the actual road networks.However, the Dijkstra algorithm has great redundancy in solving the shortest-path problem, especially for the large-scale urban road networks, when considering the time complexity of the Dijkstra algorithm is 2O(n).The optimization algorithm, which is optimized in the data storage structure and search strategies, is the most direct and effective method to reduce the storage space and the running time of the shortest path algorithm. In order to reduce the running time, the redundancy and the complexity of the algorithm, the article mainly aims at the simple and necessary optimization of Dijkstra algorithm in the aspect of data storage and focuses on the research and verification of the shortest path optimization algorithm which is used in the actual road networks based on rectangular search and bidirectional search.There are three main contents of this paper, including the following several aspects:(1) The traffic data preprocessing of the actual road networks. It consists mainly of proposing the processing method of the latitude and longitude data, including the road length calculation, which is according to the latitude and longitude data, and the process of converting the latitude and longitude data to Cartesian representation, and then summarizing the characteristics of the actual city road networks and on the basis of the above.(2) The study on the shortest path search algorithm based on the restricted search area. There are two main aspects: proposing Dijkstra algorithm based on rectangular restricted area and getting the search area and the boundary value of the rectangular search algorithm in the preprocessing data, analyzing and verifying the validity and reliability of this algorithm.(3) The research on the shortest path algorithm based on bidirectional search. This paper includes the proposal of the termination conditions of bidirectional search as well as the theoretical proof about the reliability and validity of the termination conditions.