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 and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.
