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 al...

Full description

Saved in:
Bibliographic Details
Main Authors: Wenyan Zhou, Qizhi Qiu, Peng Luo, Pei Fang
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Complexity theory
Dijkstra algorithm
Heuristic algorithms
Navigation
orientation rectangle
restricted searching area
Roads
shortest path
Software
Software algorithms
statistical parameter of urban road network
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
DOI:10.1109/CSCWD.2013.6581044