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

[[abstract]]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.[[note]]SC