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(n2.5Slog3n) 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⋅nlog3n) 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˜(S⋅k⋅n2)1 and a query bound of O˜(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˜(S⋅k⋅n2) and a query bound of O˜(n2/k2), 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.