A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

作者：Kao Kuo Hua; Chang Jou Ming; Wang Yue Li^*; Juan Justie Su Tzu

来源：Algorithmica, 2011, 61(2): 402-418.

DOI：10.1007/s00453-010-9402-4

• Strictly-second-shortest paths
• Next-to-shortest paths
• Graph algorithms

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an an O(n(2)) time algorithm for solving this problem, which significantly improves the bound of a previous one in O(n(3)) time where n is the number of vertices in G.

• 出版日期2011-10