ALCOMFT-TR-01-23

C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela and U. Nanni
Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study
Rome. Work package 5. March 2001.

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.

Postscript file: ALCOMFT-TR-01-23.ps.gz (165 kb).