Shortest paths on dynamic graphs

Among the variants of the well-known shortest path problem, those that refer to dynamically changing graphs are theoretically interesting, as well as computationally challenging. Application-wise, there is an industrial need for computing point-to-point shortest paths on large-scale road networks whose arcs are weighted with a travelling time that depends on traffic conditions. We survey recent techniques for dynamic graph weights as well as dynamic graph topology.