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
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.