2002, (2): 188-191.
摘要:
针对城市道路网图节点数较多, 经典的求解最短路径的 Dijkstra算法存在计算时间较长的问题. 对矢量化的城市道路网图的特点进行分析, 给出了道路网图的计算机存储结构, 提出一种快速求解城市道路网两节点间的最短路径近似算法. 算法的实现采用双向式搜索法、投影法和夹角最小的方法. 理论分析和实验结果表明, 和Dijkstra算法相比, 该算法尽管有时得不到最优解, 但能大大减小搜索空间, 提高搜索速度, 时间复杂性不超过O( N ), 适用于车辆导航系统