扇形优化Dijkstra算法

Sector Optimization Dijkstra Algorithm

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

All temporary marked nodes are searched many times in Dijkstra algorithm. It becomes bottleneck obviously. An optimization algorithm is presented in this paper baaed on the analysis of Dijkstra＇s algorithm. It searches the shortest path within the sector limit because searching area and searching direction are limited. In the course of the optimization algorithm running, these nodes away from the shortest path are abandoned and those nodes close to goal from direction or position are processed. It finds a shortest path according to start node, goal node and angle of searching sector given by user. So the number of processed nodes is largely reduced in the optimization algorithm. Speed and efficiency of the optimizaton algorithm are improved.