Abstract
We present the first experimental study of the fully dynamic single-source shortest paths problem in digraphs with arbitrary (negative and non-negative) arc weights. We implemented and tested several variants of the theoretically fastest fully dynamic algorithms proposed in the literature, plus a new algorithm devised to be as simple as possible while matching the best worst-case bounds for the problem. According to experiments performed on randomly generated test sets, all the considered dynamic algorithms are faster by several orders of magnitude than recomputing from scratch with the best static algorithm. The experiments also reveal that, although the simple dynamic algorithm we suggest is usually the fastest in practice, other dynamic algorithms proposed in the literature yield better results for specific kinds of test sets.
Partially supported by the IST Programme of the EU under contract n. IST-1999- 14186 (ALCOM-FT).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.
D. Alberts, G. Cattaneo, and G. F. Italiano. An empirical study of dynamic graph algorithms. ACM Journal on Experimental Algorithmics, 2:Article 5, 1997.
G. Amato, G. Cattaneo, and G. F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. In ACM-SIAM Symp. on Discrete Algorithms, pp. 1–10, 1997.
B. V. Cherkassky and A. V. Goldberg. Negative-cycle detection algorithms. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1136, pp. 349–363, 1996.
B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73:129–174, 1996.
J. Edmonds, R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19:248–264, 1972.
P. G. Franciosa, D. Frigioni, and R. Giaccio. Semi-dynamic shortest paths and breadth-first search on digraphs. In Symp. on Theoretical Aspects of Computer Science. Lect. Notes in Comp. Sc. 1200, pp. 33–46, 1997.
D. Frigioni, M. Ioffreda, U. Nanni, G. Pasqualone. Experimental Analysis of Dynamic Algorithms for the Single Source Shortest Path Problem. ACM Journal on Experimental Algorithmics, 3:Article 5 (1998).
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 34(2):351–381, 2000.
D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Fully dynamic shortest paths and negative cycles detection on digraphs with arbitrary arc weights. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1461, pp. 320–331, 1998.
D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Shaefer, C. Zaroliagis. An experimental study of dynamic algorithms for directed graphs. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1461, pp. 368–380, 1998.
A. V. Goldberg. Selecting problems for algorithm evaluation. In Workshop on Algorithm Engineering. Lect. Notes in Comp. Sc. 1668, pp. 1–11, 1999.
A. V. Goldberg, and T. Radzik. A heuristic improvement of the Bellman-Ford algorithm. Applied Math. Letters, 6:3–6, 1993.
K. Mehlhorn and S. Naher. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96–102, 1995.
G. Ramalingam. Bounded incremental computation. Lect. Notes in Comp. Sc. 1089, 1996.
G. Ramalingam and T. Reps. On the computational complexity of dynamic graph problems. Theoretical Computer Science, 158:233–277, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., Nanni, U. (2001). Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study. In: Näher, S., Wagner, D. (eds) Algorithm Engineering. WAE 2000. Lecture Notes in Computer Science, vol 1982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44691-5_19
Download citation
DOI: https://doi.org/10.1007/3-540-44691-5_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42512-0
Online ISBN: 978-3-540-44691-0
eBook Packages: Springer Book Archive