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

An Improved Dijkstra Algorithm in Embedded-GIS System

针对嵌入式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