一种改进的Dijkstra算法应用于嵌入式GIS系统

• 作者: 张雪燕 杨晟刚 黄寅
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: Dijkstra算法 单源最短路径算法 多源最短路径算法 嵌入式GIS 前趋表
• 年，卷（期）: 2007,（2）
• 所属期刊栏目: 嵌入式应用技术
• 页码范围: 412-414
• 页数: 3页
• 分类号: TP301.6
• 字数: 2486字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7024.2007.02.055

摘要

在实践中,Dijkstra算法是处理道路网络的最有效的算法之一.但Dijkstra算法每次都需要扫描节点集合中的所有节点,降低了算法效率.通过对前人的成果和嵌入式系统的性能进行研究和分析后,分两步来提高算法效率:第1步通过数据的预处理缩小算法的搜索范围;第2步为每个节点添加属性值、增加前趋表,以辅助算法快速找到一条最短路径.然后将此算法应用于嵌入式GIS系统中,并使用大量的数据进行测试,结果表明改进的算法明显提高了GIS系统的效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张雪燕	宁波广播电视大学信息系	26	54	4.0	6.0
2	黄寅	宁波广播电视大学信息系	9	94	5.0	9.0
3	杨晟刚	中国科学院自动化研究所复杂实验室	2	24	2.0	2.0