ALCOMFT-TR-01-150

C. Demetrescu and G.F. Italiano
Fully Dynamic All Pairs Shortest Paths with Real Edge Weights
Rome. Work packages 2 and 4. June 2001.

Abstract: We present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates deterministically in O(S· n^2.5log³ n) amortized time and queries in optimal worst-case time. No previous fully dynamic algorithm was known for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error which supports updates faster in O(S· nlog³ n) amortized time.

Postscript file: ALCOMFT-TR-01-150.ps.gz (112 kb).