改进Dijkstra算法在嵌入式GIS系统中的应用研究
PDF下载 (341)梁 骥,张雪燕.改进Dijkstra算法在嵌入式GIS系统中的应用研究[J].宁波大学学报(理工版),2013,26(01):53-56.DOI:
LIANG Ji,ZHANG Xue-yan.An Improved Dijkstra Algorithm in Embedded-GIS System[J].Journal of Ningbo University(Natural Science & Engineering Edition),2013,26(01):53-56.DOI:
| Title: | An Improved Dijkstra Algorithm in Embedded-GIS System |
| 作者: | 梁 骥, 张雪燕 |
| Author(s): | LIANG Ji, ZHANG Xue-yan |
| 关键词: | Dijkstra算法; 椭圆限制搜索区域算法; 嵌入式地理信息系统; 前趋表 |
| Keywords: | Dijkstra; elliptic restricted area-searching algorithm; embedded-GIS; priority table |
| 分类号: | TP301.6 |
| 文献标识码: | A |
| 摘要: | 针对嵌入式GIS系统的特点对经典Dijkstra算法进行优化处理. 分两步以提高算法效率, 第一步采用椭圆限制区域算法来缩小算法的搜索范围; 第二步为每个结点添加属性值、增加前趋表, 以辅助算法快速找到一条最短路径. 最后将此算法应用到嵌入式GIS系统中, 测试结果表明: 在城市道路网络中, 改进的算法大大提高了嵌入式GIS系统的效率. |
| Abstract: | For the embedded system, a more efficient implementation of Dijkstra algorithm for embedded geographic information system is presented. The algorithm’s efficiency is improved by two steps: first, reduce the scanning scale by applying elliptic restricted area-searching algorithm; second, add property value to each node and a priority table, which helps the algorithm to find a shortest path quickly. The improved algorithm is applied to the given embedded-GIS system, which suggests the improvement of the efficiency of the embedded- GIS system greatly in urban road networks. |
| 参考文献 /References: | [1] Zhan F B. Three fastest shortest path algorithms on real road networks: Data structures and procedures[J]. Journal of Geographic Information and Decision Analysis, 2001, 1(1):69-82. [2] 陆锋, 卢冬梅, 崔伟宏. 交通网络限制搜索区域时间最短路径算法[J]. 中国图象图形学报, 1999, 4(10):849-853. [3] 王开义, 赵春江, 青桂仙, 等. GIS领域最短路径搜索问题的一种高效实现[J]. 中国图象图形学报, 2003, 8(8):951-956. [4] 王海梅, 周献中. 网络系统中的最短路径分析及其应用研究[J]. 兵工学报, 2006, 27(3):515-518. [5] 陆锋. 最短路径算法: 分类体系与研究进展[J]. 测绘学报, 2001, 30(3):269-275. [6] Wayne Wolf. 嵌入式计算机系统设计原理[M]. 北京: 机械工业出版社, 2002. [7] Stig N, Bengt R. Computer cartography shortest route programs[M]. Sweden: The Royal University of Land, 1969. [8] 崔伟宏. 空间数据结构研究[M]. 北京: 中国科学技术出版社, 1995. |
| 备注/Memo: | 收稿日期: 2012?09?05. 第一作者: 梁 骥（1978－）, 男, 安徽合肥人, 硕士/实验师, 主要研究方向: 多媒体信息技术. E-mail: lj@nbtvu.net.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
