改进Dijkstra算法在嵌入式GIS系统中的应用研究  

An Improved Dijkstra Algorithm in Embedded-GIS System

作　　者：梁骥[1] 张雪燕[1] 

机构地区：[1]宁波广播电视大学文法系,浙江宁波315000

出　　处：《宁波大学学报（理工版）》2013年第1期53-56,共4页Journal of Ningbo University：Natural Science and Engineering Edition

摘　　要：针对嵌入式GIS系统的特点对经典Dijkstra算法进行优化处理.分两步以提高算法效率,第一步采用椭圆限制区域算法来缩小算法的搜索范围;第二步为每个结点添加属性值、增加前趋表,以辅助算法快速找到一条最短路径.最后将此算法应用到嵌入式GIS系统中,测试结果表明:在城市道路网络中,改进的算法大大提高了嵌入式GIS系统的效率.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 svstem ~reatlv in urban road networks

关 键 词：DIJKSTRA算法 椭圆限制搜索区域算法 嵌入式地理信息系统 前趋表 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]