An algorithm for the preprocessing shortest path problem

Given a directed network, a designated arc, and lower and upper bounds for the distance of each arc, the preprocessing shortest path problem is a decision problem that decides whether there is some choice of distance vector such that the distance of each arc honors the given lower and upper bound restriction, and such that the designated arc is on some shortest path from a source node to a destination node with respect to the chosen distance vector. The preprocessing shortest path problem has many real world applications such as communication and transportation network management and the problem is known to be NP-complete. In this paper, we develop an algorithm that solves the problem using the structural properties of shortest paths.