摘要： 从城市道路网的特点出发，描述了矢量化的城市道路网的存储结构，提出一种求解城市道路网两节点间最短路径的算法。算法基于双向式搜索原理，采用投影法、夹角最小的方法及二叉树理论。和Dijkstra算法相比，算法大大减小搜索空间，提高搜索速度，时间复杂性不超过O(N)，N为网络节点数。实际应用表明算法有很强的实用性和可靠性。

关键词: 短路径, 路径规划, 城市道路网

Abstract: According to the characteristics of a city road net, this paper discusses a kind of data structure of road net and proposes an algorithm for seeking the shortest path between two points in the road net. The algorithm takes advantage of the theories of bidirectional search, projection, minimum angle and binary tree. Compared with Dijkstra algorithm, the algorithm can reduce seeking space and can raise seeking speed greatly, and its time complexity can not exceed O(N), while N is the number of road net points. The application results show that the algorithm has good practicability and reliability.

中图分类号: 

• TP301.6