论文部分内容阅读
车辆导航系统的最基本功能是最短路径的搜索，车载导航是单源单目标的最短路径算法的重要应用之一．传统的Dijkstra算法是一种典型的单源最短路径算法，因为实际系统的实时要求，有必要改进Dijkstra算法．基于对时间和空间复杂度的分析，提出一种新型的Dijkstra改进算法，具有高效性．其改进分3个方面：采用邻接表作为道路网络拓扑的存储结构；利用二叉堆实现优先队列；根据节点的分布情况将搜索过程分为几个阶段，引入了动态限制搜索区域机制．最后在实际道路网络中的测试及仿真结果表明了改进算法的可行性和优越性．