摘要
针对城市道路网图节点数较多 ,经典的求解最短路径的 Dijkstra算法存在计算时间较长的问题 .对矢量化的城市道路网图的特点进行分析 ,给出了道路网图的计算机存储结构 ,提出一种快速求解城市道路网两节点间的最短路径近似算法 .算法的实现采用双向式搜索法、投影法和夹角最小的方法 .理论分析和实验结果表明 ,和Dijkstra算法相比 ,该算法尽管有时得不到最优解 ,但能大大减小搜索空间 ,提高搜索速度 ,时间复杂性不超过O( N ) 。
The computing time of the Dijkstra algorithm which is considered a typical algorithm for the shortest path computation is relatively long, if a city's road net map has many nodes. To improve the situation, the characteristics and data structure of the vector map of a city's road net are discussed, and then a quick approximate algorithm for the shortest path between two nodes in a city's road net is proposed. The algorithm takes advantage of the methods of bidirection, projection and minimum angle. Analysis in theory and experimental results show that compared with the Dijkstra algorithm, although the new algorithm cannot reach the optimum occasionally, it can greatly reduce the seeking space and increase the seeking speed. Its time complexity can not exceed O(N) , and can well be applied to vehicle navigation systems.
出处
《北京理工大学学报》
EI
CAS
CSCD
北大核心
2002年第2期188-191,共4页
Transactions of Beijing Institute of Technology
基金
兵科院预研项目
