On the k Shortest Simple Paths Problem Using Biobjective Search

Max Huneshagen (), Pedro Maristany de las Casas (), Antonio Sedeño-Noda () and Ralf Borndörfer ()
Additional contact information
Max Huneshagen: Freie Universität Berlin
Pedro Maristany de las Casas: Zuse Institute Berlin
Antonio Sedeño-Noda: Estadística e Investigación Operativa, Universidad de La Laguna
Ralf Borndörfer: Zuse Institute Berlin

Chapter Chapter 42 in Operations Research Proceedings 2023, 2025, pp 325-330 from Springer

Abstract: Abstract The k simple shortest paths problem (kSSP) on a simple weighted digraph is a classic combinatorial problem. Although Yen’s algorithm no longer possesses the best known time complexity, it remains an important benchmark for kSSP algorithms. Roditty and Zwick developed a kSSP algorithm that solves the problem by solving 2k instances of 2SSP. However, the authors do not specify how to solve this subroutine efficiently. We close this gap by providing a new biobjective search algorithm for 2SSP. The algorithm by Roditty and Zwick in conjunction with our new algorithm matches the running time bound of Yen’s algorithm and is fast in practice. Moreover, we discuss the framework of the asymptotically fastest kSSP algorithm due to Gotthilf and Lewenstein and use it in connection with a recent breakthrough result on the all pairs shortest paths problem by Orlin and Végh to show the existence of an O(kmn) algorithm for kSSP for integer costs. This improved time complexity bound is the best known for this relevant special case. In our computational experiments on road and grid graphs we assess the new algorithm’s practical efficiency. It turns out to be significantly faster than Yen’s algorithm on these graphs.

Keywords: Shortest paths problem; Network optimisation; Algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-58405-3_42

Ordering information: This item can be ordered from
http://www.springer.com/9783031584053

DOI: 10.1007/978-3-031-58405-3_42

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().