An Inverse Shortest Path Problem on an Uncertain Graph

Abstract

The inverse shortest path problem is to minimize the modification on the edge weights such that a predetermined path becomes the shortest one from the origin to the destination with respect to the new edge weights. In this paper, the inverse shortest path problem is considered on a graph with uncertain edge weights. It is shown that the model of the uncertain inverse shortest path problem can be transformed into a deterministic counterpart and then be solved efficiently. A numerical example is presented as well for illustration.