Time Shortest Path Algorithm for Restricted Searching Area in Transportation Networks
交通网络限制搜索区域时间最短路径算法

Transportation networks have apparent characteristics of spatial distribution, which is the basic difference between the sparse graphs describing the transportation networks and other planar graphs describing topological structure or hierarchical structure. A time shortest path algorithm based on the restricted searching area is presented in this paper. On the basis of quadary priority queue and inverse adjacent list data structure, a restricted searching area algorithm is established, based on the statistical analysis on the spatial distribution of transportation networks, with the appropriate restricted ellipse and rectangle areas for appointed start and destination nodes. The restricted rectangle searching area is proved more appropriate as the restricted area. Considering the different road travelling impedance and turn impedance, a time shortest path algorithm is presented. The presented algorithms can efficiently decrease the searching scale and improve the running efficiency. It has been proved by some tests on the real-world transportation network.