Improved algorithm for finding next-to-shortest paths

DOI10.1016/j.ipl.2006.04.013zbMath1185.68489OpenAlexW2052950624MaRDI QIDQ845719

Guangzhong Sun, Shi-Sheng Li, Guo-Liang Chen

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.04.013

zbMATH Keywords

computational complexityshortest pathsgraph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Simple paths with exact and forbidden lengths ⋮ A simpler and more efficient algorithm for the next-to-shortest path problem ⋮ A quadratic algorithm for finding next-to-shortest paths in graphs ⋮ An efficient algorithm to find next-to-shortest path on permutation graphs

Cites Work

• Computing strictly-second shortest paths
• Finding next-to-shortest paths in a graph

This page was built for publication: Improved algorithm for finding next-to-shortest paths