License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.18
URN: urn:nbn:de:0030-drops-120925
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12092/
Go to the corresponding LIPIcs Volume Portal

Al Zoobi, Ali ; Coudert, David ; Nisse, Nicolas

Space and Time Trade-Off for the k Shortest Simple Paths Problem

pdf-format:
LIPIcs-SEA-2020-18.pdf (0.6 MB)

Abstract

The k shortest simple path problem (kSSP) asks to compute a set of top-k shortest simple paths from a vertex s to a vertex t in a digraph. Yen (1971) proposed the first algorithm with the best known theoretical complexity of O(kn(m+n log n)) for a digraph with n vertices and m arcs. Since then, the problem has been widely studied from an algorithm engineering perspective, and impressive improvements have been achieved.
In particular, Kurz and Mutzel (2016) proposed a sidetracks-based (SB) algorithm which is currently the fastest solution. In this work, we propose two improvements of this algorithm.
We first show how to speed up the SB algorithm using dynamic updates of shortest path trees. We did experiments on some road networks of the 9th DIMAC'S challenge with up to about half a million nodes and one million arcs. Our computational results show an average speed up by a factor of 1.5 to 2 with a similar working memory consumption as SB. We then propose a second algorithm enabling to significantly reduce the working memory at the cost of an increase of the running time (up to two times slower). Our experiments on the same data set show, on average, a reduction by a factor of 1.5 to 2 of the working memory.

BibTeX - Entry

@InProceedings{alzoobi_et_al:LIPIcs:2020:12092,
  author =	{Ali Al Zoobi and David Coudert and Nicolas Nisse},
  title =	{{Space and Time Trade-Off for the k Shortest Simple Paths Problem}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12092},
  URN =		{urn:nbn:de:0030-drops-120925},
  doi =		{10.4230/LIPIcs.SEA.2020.18},
  annote =	{Keywords: k shortest simple paths, graph algorithm, space-time trade-off}
}

Keywords: k shortest simple paths, graph algorithm, space-time trade-off
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: The code of our algorithms is publicly available at https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI