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

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 ${\mathcal{O}}(n^{2})$ time algorithm for solving this problem, which significantly improves the bound of a previous one in ${\mathcal{O}}(n^{3})$ time where n is the number of vertices in G. [ABSTRACT FROM AUTHOR]