机构地区: 吉林大学交通学院
出 处: 《吉林大学学报(工学版)》 2006年第1期123-127,共5页
摘 要: 现有的最短路径搜索算法如D ijkstra算法或椭圆限制的D ijkstra算法等计算效率较低,有待进一步改进。作者在椭圆限制的D ijkstra算法基础上,通过对椭圆进行线性化处理和对限制用的多边形进行优选,得出一种平行四边形限制的最短路径算法,使搜索效率有了较大程度的提高,通过对各种算法的运行结果进行对比,证明了本算法的有效性和快速性。 The operating efficiencies of the existing shortest path searching algorithms such as Dijkstra algorithm and Dijkstra algorithm on the limiting ellipse, etc., are low and inconvenient in practical application, so they need to be improved. On the basis of the Dijkstra algorithm on the limiting ellipse, by means of linearizing the-ellipse and optimizing the limiting polygon, an optimal path algorithm based on the limiting parallelogram was proposed to improve significantly the searching efficiency. The comparison results of free searching and searching by ellipse method and parallelogram method proved the efficiency and validity of the parallelogram method.