Dijkstra Shortest Algorithm Research Based On GIS Spacial Distribution

With the prevalence of computer and the development of geography information,GIS was applied thoroughly and widely.GIS network path analysis is the hotspot of GIS research, and the shortest path is the most basic and the most pivotal problem,it has many directly application,so the research on it was never interrupted. The effective combine of classical graph theory with computer data structure and algorithm which develop perfectly has unceasingly made new shortest path algorithms emerges. They have each characteristic in respect of space complexity, time complexity, easy realization and applying range.Dijkstra algorithm is the basic theory of most systems solving the shortest path problem present.The excellence of Dijsktra algorithm is easy programming and strong compatibility. But it is not aiming at two spots, and in the process of finding shortest path in GIS we usually want to find the shortest path of two special spots, so the efficency of this algorithm is low. In addition traditional Dijkstra algorithm adopt the adjacency matrix data structure which ocupys enormous space and wastes the computer resource gravely so it is unsuitable for immenseity node amounts of GIS .Therefore, in the actual application of GIS, it's necessary to improve the shortest path algorithm based on Dijkstra direct to practical situation.Exsiting application system adopts a lot of different mehod 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 efficency of Dijkstra algorithm this thesis, by analyzing the Dijkstra shortest path algorithm, fully utilize special distribution characteristic in GIS, appoint to the applicaction 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 realzition of classical Dijkstra algorithm.Discuss search policy of ichnography.Classify the shortest path algorithm sysmeticly from three aspects including problem type, network type and realization method.â‘¡Research the data structure in GIS.Analyse 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 paralley.â‘£Study the GIS special distribution feature.Considering the concrete conditions of finding the shortest path in GIS road traffic, this paper analyse 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..