摘要
针对传统Dijsktra算法运算需耗费大量的内存空间和运算时间,难以满足GIS这种大数据量的路径选择要求,提出一种改进的Dijsktra算法。该算法采用利于实现的结点-关联弧段优化存储结构,从传统算法的临时结点中,将大量与永久结点不直接连通的点划分为未标记结点,很大程度上减少了临时结点的数量,提高了算法的搜索效率,同时,运算时通过拓扑索引和临时文件缓冲,大大节省了内存空间,使得算法的空间复杂度为O(n)。试验和实际应用结果证明了算法的有效性。
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.
出处
《计算机应用与软件》
CSCD
2011年第5期275-277,共3页
Computer Applications and Software
