Research On Shortest Path Algorithm Based On Graph In Dynamic Navigation System

In recent years, there have been more and more vehicles, traffic demand and traffic flow in cities with the development of our country's economic.In this situation, dynamic navigation system can plan an optimal path under the real time traffic information, which avoid the traffic congestion,and then save the travelling cost and do good to the whole traffic network.The development of this real time navigation system has come with real time path planning.This research looks at the use of dynamic travel time of road segment, obtained from a traffic information center. This on-road travel time reflects the average roadway speed and the level of congestion.This paper discusses the vector map representation in traffic road network, shortest path algorithm and the solution of optimal path planning.At first, this research introduced the concept of GIS involved of it's data model, organization and management of GIS data, elementary function etc,analyzed vector map representation of the city road traffic network, the description of limitation of real traffic network.Then, this paper introduced the correlative concept of graph theory, including the data structure of graph, and analysed graph search, including the general graph search based on fringe,breadth-first search based on FIFO queue and depth-first based on stack.On the same time analysed the Dijkstra algorithm which is applied in computing single-source shortest path and Euclidean heuristic which is used in traffic network.In the end, this paper studied the algorithm and complexity of time shortest path.analyzed A* algorithm which can decrease the time complexity and improve the efficiency of algorithm.It confirmed the method of gaining the road segment travel time and the storage travel time serial and considered the solution of real time path planning in dynamic navigation system.