An improved shortest path algorithm based on orientation rectangle for restricted searching area

摘要

High complexity of Dijkstra Algorithm limits its application in searching the shortest path in road network. Thus it is necessary to improve the efficiency of searching the shortest path in road network. Combining the existing conventional algorithms for restricted searching area, a shortest path algorithm based on cut-corner orientation rectangle is proposed. Based on orientation rectangle, the algorithm intends to cut corresponding corner areas so as to shrink the searching area. The proposed algorithm makes full use of the statistical parameter of urban road network to gain a reasonable value of the cut-angle. Theoretical calculation and experiment results are presented. All show that the proposed algorithm can apparently enhance the efficiency of searching the shortest path, which can reduce the time-complexity by 10–40% without influencing its reliability compared with existing conventional algorithms.