GIS中使用改进的Dijkstra算法实现最短路径的计算

地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等，而最短路径分析是其中关键的环节，因而对其算法进行优化很有必要，为此在传统的最短路径算法，即Ｄｉｊｋｓｔｒａ算法的基础上，采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作，从而提高了该算法的分析效率。讨论了地理网络数据的组织结构和最短路径的具体实现过程，并引入了相关概念，并引入了相关概念，通过具体案例分析表明，改进算法在提高网络系统空间分析效率方面是可行的。

The Calculation of the Shortest Path Using Modified Dijkstra Algorithm in GIS

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.