The single most vital arc in the most economical path problem-A parametric analysis

For a network with two specified nodes, an arc is called a single most vital arc in the shortest path problem, if its removal from the network results in the greatest increase in the shortest distance between the specified nodes. In this paper, the authors consider the single most vital arc in a generalized shortest path problem, called the most economical path problem, in which the cost for transshipping λ units of cargo along an arc depends on λ. Clearly, the single most vital arc in the most economical path problem depends on λ. Moreover, λ changes frequently in practical applications. The authors propose an algorithm to find the single most vital arcs in the network for all possible values of λ.