The Calculation of the Shortest Path Using Modified Dijkstra Algorithm in GIS
GIS中使用改进的Dijkstra算法 实现最短路径的计算

In GIS it is necessary to optimize the analysis function of the shortest path as the hinge of spatial network analysis, which includes shortest path analysis, resource allocation and isochrone, and so on. Here derived from the traditional calculating method, i.e. Dijkstra algorithm, the analysis procedure of the shortest path is improved by adopting the data structure of binary heap to complete the operation of priority queue. Initialization, Extraction, and Relzxztion. The topological structure of geographical network data and the detailed implementing steps of the shortest path are also discussed. Furthermore, the visualizing calculation of the shortest path is completed by COM(Component Object Model) techniques, and the calculating procedure is encapsulated into the component of the geographic network class. The complexity analysis and the case of this algorithm showes that the modified algorithm is applicable to improve the efficiency of spatial analysis of the net system.