摘要
Dijkstra算法是计算最短路径的典型算法,它能得出最短路径的最优解,但因为遍历计算的节点很多,所以效率低下。针对此局限性,提出一种基于方向判别的较优路径选择算法。该算法利用交通网络的方向特性,能够快速收敛找到较优路径,提高选路算法的性能。引入偏差率和吻合率等概念来描述算法,对其设计与实现过程进行详细的阐述,并利用MATLAB进行仿真实验。实验结果表明该算法在性能上优于Dijkstra算法,尽管得出的路径不一定是最优路径,会存在偏差,然而这些偏差是可以容忍的,不会影响算法的价值。
Dijkstra algorithm is a typical shortest path algorithm.It can get an optimal solution for shortest path.However since it traverses lots of nodes,its efficiency is poor.For such a limitation,a direction discrimination based better path selection algorithm is proposed.The algorithm takes advantage of traffic network’s directional characteristics to be able to achieve fast convergence to find out a better path so that the performance of the path selection algorithm is improved.Such concepts as deviation ratio and inosculation ratio are introduced to describe the algorithm.The design and implementation process of the algorithm is elaborated in detail while simulation experiments are carried out with Matlab.Experimental results show that the algorithm performs better than Dijkstra algorithm.Although the obtained path may not be optimal so that there may be some deviations,these deviations can be tolerated for they won’t devalue the algorithm.
出处
《计算机应用与软件》
CSCD
北大核心
2012年第6期94-96,108,共4页
Computer Applications and Software
基金
国家级大学生创新性实验项目(101067305)
关键词
较优路径
交通方向
可选下一跳集
选路点
Better path Traffic direction Optional next hop set Path selection corner
