Implementation and Evaluation of the Shortest Path Labeling Algorithms in Transportation Networks
Feng Lu · 2005
Labeling algorithms have got broad applications for shortest path finding in transportation networks,among which various fine-tunned Dijkstra's algorithms well known as typical label setting algorithms have been selected by many GIS related software for network analysis.However,label correcting algorithms,the other group in label algorithms family,are rarely used yet in GIS network analysis.After detailed discussion on the structures of labeling algorithms,in this paper,the implementation,complexity and applicability of labeling setting and label correcting algorithms are analyzed.Then three best-known fastest label algorithms,i.e.,Dijkstra algorithm implemented with approximate buckets(DIKBA),Dijkstra's algorithm based on quad-heap priority queue(DIKQH) and Pallottino algorithm(TWO_-Q),were used to carry out practical evaluation on three real urban road networks.The results showed that for one-to-one shortest path calculation,DIKQH and DIKBA greatly outperformed than TWO-Q algorithm,and DIKQH exhibited the best running efficiency.For one-to-all shortest path calculation,however,TWO-Q algorithm runs a little faster than DIKQH and DIKBA on the selected real road networks.The author argued that more attention should be paid on TWO-Q algorithm for its efficiency and applicability.