Fully dynamic all pairs shortest paths with real edge weights

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 in O(n(2.5)root/S log(3) n) amortized time and queries in optimal worst-case time. This algorithm is deterministic: no previous fully dynamic algorithm was known before for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error that supports updates faster in O (S . n log(3) n) amortized time. We also show how to obtain query/update trade-offs for this problem, by introducing two new families of randomized algorithms. Algorithms in the first family achieve an update bound of (O) over tilde (S . k . n(2))(1) and a query bound of (O) over tilde (n/k), and improve over the previous best known update bounds for k in the range (n/S)(1/3) <= k < (n/S)(1/2). Algorithms in the second family achieve an update bound of <(O)over tilde>(S . k . n(2)) and a query bound of (O) over tilde (n(2)/k(2)), and are competitive with the previous best known update bounds (first family included) for k in the range (n/S)(1/6) <= k < (n/S)(1/3). (C) 2006 Elsevier Inc. All rights reserved.