Shortest paths on dynamic graphs
Giacomo Nannicini, Leo Liberti · International Transactions in Operational Research · 2008
Abstract 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.