Shortest path problems: A parametric study

The shortest path problem is one of the fundamental problems in the area of network programming and many efficient algorithms have been proposed in the literature. Two important sensitivity issues have been discussed. One is the problem of updating shortest paths when nodes are added or deleted and when the lengths of some arcs are increased or decreased. The other is the problem of calculating arc tolerances, that is, the maximum increase or decrease in the length of a single arc without changing a given optimal tree. However, in network applications, a node often serves as a decision point and the arcs emanating from this node represent possible alternatives, the costs of which naturally depend on some attribute or parameter of the decision point. In this situation, any perturbation in the parameter may affect the alternative costs in a dependent and simultaneous fashion. A proper sensitivity analysis should be capable of handling these simultaneous changes in arc costs. In this paper, it is assumed that there exists a parameter of interest whose perturbation causes the simultaneous changes in arc lengths. It is hoped to find the invariance condition on these simultaneous changes such that the shortest path between two specified nodes remains unchanged. The invariance condition is then applied to derive the sensitivity range of the parameter. Computational aspects are discussed and numerical examples are presented. [In Korean.]