The Application And Research Of The Shortest Path Algorithm Based On WebGIS

Since 1960s, a Canadian expert on survey put forward the concept---GIS, it has been developed well enough in decades. With the popularization of internet ,GIS has been widened by the function of WWW, and turned into an implement for the public. From any point of WWW, users can skim through special statistics, draw up specialized pictures, and carry on various spatial research as well as spatial analysis through WebGIS. The purpose of the latter two is to conduct the inquiry and analysis in GIS system so that to offer the information for supporting some decision .This paper begins from the algorithm of shortest path, the essential algorithm in spatial analysis, and makes a comparison with the traditional algorithms of shortest path. By thoroughly analyzing the thinking of various algorithms, the storage of data structure and the complexity of searching time, this paper mean to point out the weakness and shortcomings of the traditional algorithms. On the basic research of A star instructive algorithm in artificial intelligence, an efficiently realized algorithm, instructive searching method with restrictive conditions, is put forward with regard to the problem of shortest path. This algorithm put forward a restrictive condition, i.e., "the straight line between two points is the shortest length"and use binary heaps to sort all nodes which are to be searched. In each searching process., with the help of the restrictive condition, it assesses every node being searched, and finds the best position, from which the destination is reached directly. By orientating the searching to the destination, the number of searched nodes is reduced, and the whole process is shortened. A test shows that the complexity of this algorithm is only O(n).This algorithm is put into use in the monitoring system of transportation information in Shanghai. Compared with the traditional algorithms for the shortest path, the searching time of it could be controlled in 2S. Especially when a longer path is being searched, the searching efficiency is much better than the traditional algorithms for shortest path.The narrative process of this paper is as follows:First of all, it introduces the conceptions of GIS and WebGIS, their present development and growing trend in future, including the thorough description of the mode classification and the structure method of WebGIS, as well as the developing direction of WebGIS in future. The theoretical research of various algorithms for spatial statistics is carried on, with the focus on the description of the analysis of spatial network statistics , and the comparison of the storage data structure, from which comes the conception of shortest path in the analysis of spatial network statistics .Secondly, it will present the basic skills of the algorithm for the shortest path-- marking. After comparing the traditional algorithms for shortest path, and according the three situations of the shortest path problem, this paper outlines the representative algorithm in each one, i.e., algorithm of TQQ,algorithm of Dijkstra,algorithm of Floyd. Through the detailed analysis of the calculating thinking of various algorithms, the storage data structure and the complexity of searching time, the weakness and shortcoming of the traditional algorithms are under discussion.Last, on the basis of the traditional algorithms, an efficiently realized calculating method in the shortest path is put forward, which is called an instructive searching way with restrictive condition. By theoretical test and application in reality, this algorithm is adoptable, which means that the shortest path can be reached with this algorithm. When this algorithm is put into concrete system, the searching time can be controlled within 2S. Especially when a longer path is being searching, the efficiency of searching is much better than the traditional algorithms for a shortest path.The main contribution of this paper is as follows:1) With the reference of many relevant books and material, this system puts forward the instructive searching algorithm with res...