ON SOLVING DYNAMIC SHORTEST PATH PROBLEMS
Ebrahim Nasrabadi, S. Mehdi Hashemi · 2008
Given a dynamic network with n nodes and m arcs in which all attributes including travel times, travel costs and waiting costs may change dynamically over a time horizon T. The dynamic shortest path problem is to determine a path from a specified source node to every other node with minimal total cost, subject to the constraint that the total traverse time is at most T. This problem can be formulated in two ways depending on whether a discrete or continuous representation of time is used. In this paper, we present an O(nT(n+T)) time algorithm for solving the discrete-time version of dynamic shortest path problem.