Time Expanded Network In The Hurricane Evacuation System Application

With the prevalence of computer and the development of geography information, GIS was applied thoroughly and widely due to its advantageous function.GIS network path analysis is the hotspot of GIS research,while the shortest path is the most basic and the most pivotal problem,so the research on it was never interrupted.Based on the Dijkstra algorithm combined with the GIS its own chrematistics,a lot of improvement has been adopted compared with the traditional Dijkstra algorithm.Existing application system adopts a lot of different method to improve Dijkstra algorithm based on the Dijkstra algorithm theory and the feature of GIS path analysis.Respecting the widely use of GIS and the importance of running efficiency of Dijkstra algorithm this thesis,by analyzing the Dijkstra shortest path algorithm, fully utilize special distribution characteristic in GIS,appoint to the application of finding the shortest path between two spot in GIS,and apply optimization and improvement for Dijkstra shortest path searching algorithm from the data structure, search technique and algorithm itself,and then this paper makes it more suitable to find shortest path between special spot in GIS.The main study of this paper includes:①Research main idea and realization of classical Dijkstra algorithm.Discuss search policy of ichnography.Classify the shortest path algorithm systemically from three aspects including problem type,network type and realization method.②Research the data structure in GIS.Analyze various shortest path algorithm idea,data structure it uses and the characteristic of various data structure.③Discuss the development of the shortest path algorithm in aspect of real-time and parallel.④Study the GIS special distribution feature.Considering the concrete conditions of finding the shortest path in GIS road traffic,this paper analyze the deficiency of traditional shortest path algorithm applying in the special aspect and then put forward a improved algorithm which uses GIS special distribution feature fully and take a new search method.At last,realize this improved algorithm through programming and verify validity of the algorithm through experiment.