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 $𝒪(n^2)$ time algorithm for solving this problem, which significantly improves the bound of a previous one in $𝒪(n^3)$ time where n is the number of vertices in G.