Based On A Navigation Data Shortest Path Algorithm And Application In GIS

In recent years, with the rapid development of the Geographic Information System (referred to as GIS) and the navigation technology, the combination of the two ways has been a wide range of applications in all kinds of industries in the society. The Shortest Path Computation, as the most basic and key technology in the theory and application field of the both, it is not only a research focus in the field of computer science and geographic information science, but also the priority in the applications of GIS and navigation. It has been widely used in many fields of transportation, tourism, urban planning, logistics, power electronics, navigation and others.The Shortest Path Calculation, as the theoretical basis of the calculation in the GIS network analysis and navigation features, it is not a purely theoretical shortest path computation, but rather it does with the basic of the specific navigation data and various practical constraints arc considered in practical applications. Based on it in this article, the detail of the realization and optimization method of the Shortest Path Algorithm based on the actual navigation data is discussed. Specifically, there are four aspects as follow.i The format of the navigation data that is used in this article is detailedly analysed, and on this basis, the data structures that are used in this article also are defined and organized.ii Navigation data is preprocessed, mainly including the compilation, optimization, categorized and sorted, and ultimately the formation of the data that is used in this article is formed.iii On the basic of the navigation data that is used in this article, a algorithm that prohibition rules is caculated by the tail point is designed and by this algorithm, the prohibition rules used in this article is archived.IV Based on the nodes, the sort-based topology relations among the nodes, road data and prohibition rules is established. And the speed and efficiency of the Dijkstra Algorithm is improved, according to the ascending order of the distance in all the identified nodes to all unidentified the nodes. And on the basis of it, the method to caculate the distance between any two points on the map by the Dijkstra Algorithm with prohibit rules, is archived.