Skip to Main content Skip to Navigation
Reports

Finding the k Shortest Simple Paths: Time and Space trade-offs

Ali Al Zoobi 1 David Coudert 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a source to a sink in a digraph. Yen (1971) proposed an algorithm with the best known polynomial time complexity for this problem. Since then, the problem has been widely studied from an algorithm engineering perspective. The most noticeable proposals are the node-classification (NC) algorithm (Feng, 2014) and the sidetracks-based (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant working memory. We first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with same working memory. We then propose the parsimonious SB (PSB) algorithm that significantly reduces the working memory of SB at the cost of a small increase of the running time. Furthermore, we propose the postponed nodeclassification (PNC) algorithm that combines the best of NC and SB. It offers a significant speed up compared to NC while using the same amount of working memory of NC. Our experimental results on complex networks show that all of the considered algorithms have low working memory, and that the PSB algorithm is the fastest. On road networks, the SB* algorithm is the fastest (on median) among the considered algorithms, but it suffers from a large working memory. The PNC algorithm has comparable running time to SB* on road networks while using the same working memory as NC.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03196830
Contributor : Ali Al Zoobi <>
Submitted on : Tuesday, April 13, 2021 - 11:37:15 AM
Last modification on : Saturday, May 8, 2021 - 2:02:01 PM

File

Journal-kssp.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03196830, version 1

Citation

Ali Al Zoobi, David Coudert, Nicolas Nisse. Finding the k Shortest Simple Paths: Time and Space trade-offs. [Research Report] Inria; I3S, Université Côte d'Azur. 2021. ⟨hal-03196830⟩

Share

Metrics

Record views

19

Files downloads

84