  Given an undirected graph $G=(V,E)$ with positive edge lengths and two
vertices $s$ and $t$, the next-to-shortest path problem is to find an $st$-path
which length is minimum amongst all $st$-paths strictly longer than the
shortest path length. In this paper we show that the problem can be solved in
linear time if the distances from $s$ and $t$ to all other vertices are given.
Particularly our new algorithm runs in $O(|V|\log |V|+|E|)$ time for general
graphs, which improves the previous result of $O(|V|^2)$ time for sparse
graphs, and takes only linear time for unweighted graphs, planar graphs, and
graphs with positive integer edge lengths.
