双向Dijkstra算法设计与实现
作者单位：中北大学教育部仪器科学与动态测试重点实验室 中北大学教育部仪器科学与动态测试重点实验室 中北大学教育部仪器科学与动态测试重点实验室
会议名称：《中国宇航学会深空探测技术专业委员会第四届学术年会》
会议日期：2007年
学科分类：08[工学] 080401[工学-精密仪器及机械] 081105[工学-导航、制导与控制] 0804[工学-仪器科学与技术] 0825[工学-航空宇航科学与技术] 0811[工学-控制科学与工程]
关 键 词：路径规划 最短路径 DijkStra 算法
摘 要：Dijkstra 算法一直被认为是解决最短路径问题的经典算法,然而其 O（n2）的时间复杂度却极大地限制了它的实际应用,为了在保证搜索精度的同时,提高算法的搜索效率,本文提出一种改进的 Dijkstra 算法——双向 Dijkstra 算法。文中首先介绍了该算法的原理,然后详细介绍了其设计与实现方法,最后结合路径规划算法在车辆定位导航系统中的实际应用,给出该算法的一个应用实例及其分析。结果表明本文所提出的改进算法不仅能够保证搜索精度,而且降低了时间复杂度,满足车辆定位导航系统的需要。