Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-012 (April 21, 2011)

A Polynomial-Time Algorithm for the Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
by Cong Zhang, Hiroshi Nagamochi

pdf File

Given an edge-weighted undirected graph and two vertices $s$ and $t$, the next-to-shortest path problem is to find an $st$-path whose length is minimum among all $st$-paths of lengths strictly larger than the shortest path length. The problem is shown to be polynomially solvable if all edge weights are positive, while the complexity status for the nonnegative weight case was open. In this paper we show that the problem in undirected graphs admits a polynomial-time algorithm even if all edge weights are nonnegative, solving the open problem. To solve the problem, we introduce a common generalization of the undirected graph version and the acyclic digraph version of the $k$ vertex-disjoint paths problem.