An Optimization Algorithm of Pallottino Implemented with Two Queues in Transportation Network
Feng Lu · 2006
The shortest path problem,in which label algorithms are of consequence,is a research topic in the field of geographic information science and computer science.Among label algorithms,label setting algorithms in which Dijkstra occupies the core position are always considered as the first choice in applications while label correcting algorithms are rarely used.In this paper,followed by the theory expatiation on label correcting algorithms,an optimization of the well-known Pallottino algorithm is set forward on the basis of both storage and implementation structures.The author then analyzes its time complexity and spatial complexity and finally tests its actual efficiency in Beijing transportation network.It proves a better implemental efficiency and applicability comparing with the best label setting algorithm-Dijkstra algorithm implemented with approximate buckets.As a result,it provides a good choice for network related analysis works and should be particularly useful to researchers and practitioners in operations research,transportation,and GIS.