矩形限制区域的Dijkstra改进算法  

Improved Dijkstra algorithm for restricted rectangular area

作　　者：洪进[1] 范云龙[1] 李勇华[2] 

机构地区：[1]空军预警学院,武汉430019 [2]空军空降兵学院,广西桂林541003

出　　处：《空军预警学院学报》2016年第3期207-211,共5页Journal of Air Force Early Warning Academy

摘　　要：为提高智能交通系统路径算法的效率,从搜索区域、搜索策略、数据结构、搜索过程四个方面对传统的矩形限制区域Dijkstra算法进行了改进.首先将搜索区域限制在动态的矩形区域内,人为设定一个阈值控制传统的矩形区域与动态的矩形区域的转换,然后采用先进的桶结构,最后给出了仿真实验.仿真结果表明,相比其他两种算法,改进的Dijkstra算法大大地缩短了搜索时间,且当起点和终点位于对角线上并相距较远时运行效果良好.To better the efficiency of path algorithm of intelligent traffic system （ITS）, this paper improves on Dijkstra algorithm for the traditional restricted rectangular area, in terms of such four aspects as the searching area and strategy, data structure and searching process. At first, the searching area can be restricted to a dynamic rectangular area, a threshold is set on purpose for the conversion of the traditional rectangular area to the dynamic rectangular one, and then the advanced barrel structure is employed, and finally, the simulation experiment is performed. Simulation results show that the improved Dijkstra algorithm can shorten greatly the searching time and be of better operation whilst the staring point and the terminal point are both on the diagonal and far apart.

关 键 词：路径算法 矩形限制区域 DIJKSTRA算法 桶结构 

分 类 号：TP39[自动化与计算机技术—计算机应用技术] U495[自动化与计算机技术—计算机科学与技术]