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

2011/05/03 by Bang Ye Wu · 1 citation
Computer Science · #cs.DS

paper · pdf · doi:10.1007/s00453-011-9601-7

Partial result appeared in COCOA2010

arxiv created 2011/05/03 · arxiv updated 2012/03/22

Abstract

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

Cited by

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