A Quick Path-Planning Algorithm for Vehicle Navigation System

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.