A new algorithm for reoptimizing shortest paths when the arc costschange

We propose an algorithm which reoptimizes shortest paths in a very general situation, that is when any subset of arcs of the input graph is affected by a change of the arc 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.