2026-07-22T07:15:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23248 2025-10-27T10:36:13Z ddc:004 open_access

Algorithm Engineering of SSSP with Negative Edge Weights Cassis, Alejandro Karrenbauer, Andreas Nusser, André Rinaldi, Paolo Luigi Single Source Shortest Paths Negative Weights Near-Linear Time Computing shortest paths is one of the most fundamental algorithmic graph problems. It is known since decades that this problem can be solved in near-linear time if all weights are nonnegative. A recent break-through by [Aaron Bernstein et al., 2022] presented a randomized near-linear time algorithm for this problem. A subsequent improvement in [Karl Bringmann et al., 2023] significantly reduced the number of logarithmic factors and thereby also simplified the algorithm. It is surprising and exciting that both of these algorithms are combinatorial and do not contain any fundamental obstacles for being practical. We launch the, to the best of our knowledge, first extensive investigation towards a practical implementation of [Karl Bringmann et al., 2023]. To this end, we give an accessible overview of the algorithm and discuss what adaptions are necessary to obtain a fast algorithm in practice. We manifest these adaptions in an efficient implementation. We test our implementation on a benchmark data set that is adapted to be more difficult for our implementation in order to allow for a fair comparison. As in [Karl Bringmann et al., 2023] as well as in our implementation there are multiple parameters to tune, we empirically evaluate their effect and thereby determine the best choices. Our implementation is then extensively compared to one of the state-of-the-art algorithms for this problem [Andrew V. Goldberg and Tomasz Radzik, 1993]. On the hardest instance type, we are faster by up to almost two orders of magnitude. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alejandro Cassis and Andreas Karrenbauer and André Nusser and Paolo Luigi Rinaldi 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.10 urn:nbn:de:0030-drops-232486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode