A linear time algorithm for the next-to-shortest path problem on undirected graphs with nonnegative edge lengths

Bang Ye Wu, Jun-Lin Guo, Yue-Li Wang

For two vertices $s$ and $t$ in a graph $G=(V,E)$, the next-to-shortest path is an $st$-path which length is minimum amongst all $st$-paths strictly longer than the shortest path l…