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

Preprint · Bang Ye Wu

- Archive id: arxiv:1105.0608
- Published: 2011-05-03
- DOI: https://doi.org/10.1007/s00453-011-9601-7
- arXiv: https://arxiv.org/abs/1105.0608
- Source URL: https://arxiv.org/abs/1105.0608
- PDF: https://arxiv.org/pdf/1105.0608
- Provenance: arxiv

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

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.