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

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

2011-05-03

arxiv.org/abs/1105.0608v1

Computer Science

Data Structures and Algorithms

Partial result appeared in COCOA2010

Scientific paper

10.1007/s00453-011-9601-7

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.

Affiliated with

Also associated with

No associations

Rating

A simpler and more efficient algorithm for the next-to-shortest path problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A simpler and more efficient algorithm for the next-to-shortest path problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simpler and more efficient algorithm for the next-to-shortest path problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694090