The Research And Implemention Of Shorest Path Algorithm Based On Road Networks

With the prevalence of the computer and the network, and the development of Geographical Information Science, Geographical Information System(GIS)has great application for powerful function. Network analysis, as one of the most primary function, has an impact upon many network include electronic navigation, traffic tour, city planning, electric power, communication and so on. Shortest path problem is one of the primary problems of network analyses. As the base of optimal selection problem in many fields, computing shortest paths over a network has become an important task in many transportation and network analyses systems. Shortest path analysis has been widely used in vehicle location system and city emergency systems.The paper describes some primary conceptions about the GIS, including the concept, mathematics model, the framework and manage of data, network analysis of GIS.The paper studies and tests the key techniques of shortest path analysis. We set focus on solutions which include the vector map representation of city road network, the abstraction and construction of the topological structure of network, and the efficient implementation of shortest path algorithm.Based on the fact of GIS networks, we start with construction of the topological structure of network and the realization of rapid search technology of Dijkstra algorithm, and propose the improved Dijkstra shortest algorithm, which improve the traditional operations of binary heap optimal array on the base of limiting region of using ellipse. It is based on the statistical analysis of character of city transportation space distributing, and design a reasonable limiting region of using ellipse to reduce the scale of the search of the algorithm. And it makes use of the theory that the beeline is the shortest between two points, and we get the new greedy search strategy, which is determined by the maximum degree that combined by the current node, its nearest node and destination node. At last, based on above algorithms, the algorithmis proposed. And test show that the proposed algorithm has the practicability and flexibility, could meet the requirements.