General Research on Dynamic Shortest Path Problem
Hao Ge · Journal of Dongguan University of Technology · 2009
In this paper,the shortest path problem,which has dynamic characteristic in the network combinatorial optimization field,is studied,and descriptions of dynamic shortest path problems about time and cost on discrete time model are provided.By introducing the concept of time-expanded graph,the dynamic network problem can be transformed into corresponding static shortest path problem.Then the complexities of two dynamic shortest path problems are discussed and the arithmetics given.