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

Preprint · Bang Ye Wu, Jun-Lin Guo, Yue-Li Wang

- Archive id: arxiv:1203.5235
- Published: 2012-03-23
- arXiv: https://arxiv.org/abs/1203.5235
- Source URL: https://arxiv.org/abs/1203.5235
- PDF: https://arxiv.org/pdf/1203.5235
- Provenance: arxiv

## 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.

_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.