A new algorithm for reoptimizing shortest paths when the arc costs change

We propose the first algorithmic approach which reoptimizes the shortest paths when any subset of arcs of the input graph is affected by a change of the costs, which can be either lower or higher than the old ones. This situation is more general than the ones addressed in the literature so far. We analyze the worst-case time complexity of the algorithm as a function of both the input size and the overall cost perturbation, and discuss cases for which the proposed reoptimization method theoretically outperforms the approach of applying a standard shortest path algorithm after the change of the arc costs.