A new algorithm for shortest paths in discrete dynamic networks

摘要

In this paper we study two shortest paths problems in discrete dynamic networks: the one-to-all for one departure time interval, and the all-to-one for all departure t ime intervals. Early results are revisited. New properties of these problems are established and exp0loited in developing solution algorithms. A new and simple solution algorithm for the all-to-one fastest paths problem for all departure time intervals is proposed. It is proved, anlaytically, that the new solution algorithm has an optimal running time complexity that equals the complexity of the problem. Computer implemementations and experimental evaluations of four solution algorithms support analytical results and demonstrate the efficiency of the proposed algorithm. We expect our findings to be of major benefilt to research and development activities in the field of dynamic management of large-scale transporaation systems.