计算机应用与软件2011，Vol.28Issue(5)：274-277,4.
GIS中一种改进的Dijsktra算法及其实现
AN IMPROVED DIJKSTRA ALGORITHM AND ITS REALIZATION IN GIS
张成花1
作者信息
- 1. 中国电子科技集团公司第28研究所,江苏,南京,210007
- 折叠
摘要
Abstract
The traditional Dijkstra algorithm costs a huge memory space and computation time so that it hardly satisfies the demands for the huge data volume of path selection required by GIS. An improved Dijkstra algorithm is put forward in the paper. The algorithm applies a realizable node-link arc optimized storage structure, from temporary nodes in the traditional algorithm, classifying a vast amount of nodes that are not directly connected with permanent nodes as unlabeled, so that the number of temporary nodes is greatly reduced while its searching efficiency is improved. Meanwhile by topological indexing and temporary file buffer at computing, a great deal of memory space is saved, and the spatial complexity of the algorithm is decreased to O (n). Tests and actual application results have validated that algorithm.关键词
地理信息系统/路径分析/最短路径/Dijsktra算法/文件缓冲Key words
GIS/ Path analysis/ Shortest path/ Dijkstra algorithm/ File buffer引用本文复制引用
张成花..GIS中一种改进的Dijsktra算法及其实现[J].计算机应用与软件,2011,28(5):274-277,4.
