双向Dijkstra算法设计与实现
- 作者：李杰张文栋杨卫
- 会议时间：2007-09-01
- 关键词：车辆定位导航系统 ; 路径规划 ; 最短路径 ; DijkStra算法
- 作者单位：中北大学教育部仪器科学与动态测试重点实验室,中北大学电子科学与技术系,山西太原 030051
- 母体文献：中国宇航学会深空探测技术专业委员会第四届学术年会论文集
- 会议名称：中国宇航学会深空探测技术专业委员会第四届学术年会
- 会议地点：太原
- 主办单位：中国宇航学会
- 语种：chi
摘要
Dijkstra算法一直被认为是解决最短路径问题的经典算法,然而其O(n2)的时间复杂度却极大地限制了它的实际应用。为了在保证搜索精度的同时,提高算法的搜索效率,本文提出一种改进的Dijkstra算法--双向Dijkstra算法。文中首先介绍了该算法的原理,然后详细介绍了其设计与实现方法,最后结合路径规划算法在车辆定位导航系统中的实际应用,给出该算法的一个应用实例及其分析。结果表明本文所提出的改进算法不仅能够保证搜索精度,而且降低了时间复杂度,满足车辆定位导航系统的需要。