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.