GIS中一种改进的Dijsktra算法及其实现

• 作者: 张成花
• 来源期刊: 计算机应用与软件
• 学科: 地球科学
• 关键词: 地理信息系统 路径分析 最短路径 Dijsktra算法 文件缓冲
• 年，卷（期）: 2011,（5）
• 所属期刊栏目: 算法
• 页码范围: 274-277
• 分类号: TP301.6|P208
• 字数: 2739字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2011.05.081

摘要

针对传统Dijsktra算法运算需耗费大量的内存空间和运算时间,难以满足GIS这种大数据量的路径选择要求,提出一种改进的Dijsktra算法.该算法采用利于实现的结点-关联弧段优化存储结构,从传统算法的临时结点中,将大量与永久结点不直接连通的点划分为未标记结点,很大程度上减少了临时结点的数量,提高了算法的搜索效率,同时,运算时通过拓扑索引和临时文件缓冲,大大节省了内存空间,使得算法的空间复杂度为O(n).试验和实际应用结果证明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张成花		3	4	1.0	2.0