Reoptimizing shortest paths: From state of the art to new recent perspectives
Daniele Ferone, Paola Festa, Antonio Napoletano, Tommaso Pastore · 2016
Reoptimizing shortest paths consists in solving a sequence of shortest path problems, where each problem differs only slightly from the previous one, because the origin node has been changed, some arcs have been removed from the graph, or the cost of a subset of arcs has been modified. Each problem could be simply solved from scratch, independently from the previous one, by using either a label-correcting or a label-setting shortest path algorithm. Nevertheless, a clever way to approach it is to design ad hoc algorithms that efficiently use information resulting from previous computations. This paper formally defines the different shortest path reoptimization problems arising in several different scenarios and/or conditions and surveys the most efficient state of the art algorithms to approach them. It also describes some new solution techniques inspired by the dual mathematical formulation of the problems.