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

2012/03/23 by Bang Ye Wu, Wu, Bang Ye, Jun-Lin Guo +3 · 1 citation
Computer Science · #68R10 #68W05 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #msc:68R10 #msc:68W05

paper · pdf · doi:10.48550/arxiv.1203.5235

arxiv created 2012/03/23 · arxiv updated 2012/03/26

Abstract

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 length. In this paper we show that, when the graph is undirected and all edge lengths are nonnegative, the problem can be solved in linear time if the distances from s and t to all other vertices are given. This result generalizes the previous work (DOI 10.1007/s00453-011-9601-7) to allowing zero-length edges.

Citations

• A simpler and more efficient algorithm for the next-to-shortest path problem

Cited by

• A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs

Related

• A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
• A Survey of Shortest-Path Algorithms
• Removing Sequential Bottleneck of Dijkstra's Algorithm for the Shortest Path Problem
• Finding a Shortest Non-zero Path in Group-Labeled Graphs
• The Undirected Two Disjoint Shortest Paths Problem