一种适于车辆导航系统的快速路径规划算法

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