扇形优化Dijkstra算法

摘要：

Dijkstra算法无数次遍历所有的临时标记结点,无疑成为该算法的一个瓶颈.在分析Dijkstra算法的基础上,结合平面网络的特点,从限制搜索范围和限定搜索方向两方面着手,在扇形区域内寻找最短路径,从而完成对Dijkstra算法的优化.优化算法基于有损算法,抛弃寻找最短路径时概率较小的顶点,直接寻求在方向和位置上趋向终点的顶点.它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径.因此,在优化算法中,频繁遍历的顶点数量大幅度减少,提高了算法的速度和运行效率.

关键词：GIS、最短路径、扇形优化Dijkstra算法

所属期刊栏目：16

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2007-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：49-51,54