Finding next-to-shortest paths in a graph
We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u, v)-path is a shortest (u, v)-path amongst (u, v)-paths with length strictly greater than the length of the shortest (u, v)-path. In contrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem. (C) 2004 Published by Elsevier B.V.
graph algorithms computational complexity shortest paths