限制搜索区域的距离最短路径规划算法

提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内.

A Route Planning Algorithm for the Shortest Distance Within a Restricted Searching Area

A route planning algorithm for the shortest distance in a restricted searching area, with a time complexity O(n) is proposed (n being the number of nodes in the road net). The foundation of the algorithm is that the classical Dijkstra algorithm has no directional feature during the search, and that a real city road net has its particular spatial distribution features. The algorithm takes advantage of the adjacent list data structure and the mechanism of restricted searching area, that is, the algorithm uses the spatial distribution feature of the real road network to restrict the searching area reasonably. Combining with its practical applications in real-time vehicle navigation system. An actual example is given, and the experimental results showed the time of calculation for the shortest path between any two points within the road networks can be restricted within 3 seconds by the new algorithm.