Shortest paths in a diagraph with an underestimated arc weight

Abstract

There are many real-world problems that can be modeled and solved as shortest path problems. Among them, single-pair shortest path problems appear most frequently. Sometimes the weighted digraph, in which the shortest path problem is stated, suffers a minor data change (for instance, an arc weight might increase by a given amount a) due to the changes occurring in the corresponding real-life problem. In this case, one needs to solve the shortest path problem in the modified digraph. If shortest paths are already determined in the initial digraph, these can be used as a starting point when determining shortest paths in the modified digraph or a known shortest path algorithm can be applied, from scratch, in the modified digraph. We will describe an algorithm that determines the shortest paths from a given source node s in the new weighted digraph starting from the already known shortest paths in the original weighted digraph.