Advertisement
Published in:
2009 | OriginalPaper | Chapter
Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study
Authors : Reinhard Bauer, Dorothea Wagner
Published in: Experimental Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A dynamic shortest-path algorithm is called a batch algorithm if it is able to handle graph changes that consist of multiple edge updates at a time. In this paper we focus on fully-dynamic batch algorithms for single-source shortest paths in directed graphs with positive edge weights. We give an extensive experimental study of the existing algorithms for the single-edge and the batch case, including a broad set of test instances. We further present tuned variants of the already existing
SWSF-FP
-algorithm being up to 15 times faster than
SWSF-FP
. A surprising outcome of the paper is the astonishing level of data dependency of the algorithms. More detailed descriptions and further experimental results of this work can be found in [1].