Dynamic Graphs:All-Pairs Shortest Paths

All-Pairs Shortest Paths

In this section we survey the best known algorithms for fully dynamic all pairs shortest paths (in short APSP). Given a weighted directed graph G with n vertices and m edges, the problem consists of supporting any intermixed sequence of operations of the following kind:

Update(u, v, w): updates the weight of edge (u, v) in G to the new value w (if w = +∞ this corresponds to edge deletion); Query(x, y): returns the distance from vertex x to vertex y in G, or +∞ if no path between them exists;

The dynamic maintenance of shortest paths has a remarkably long history, as the first papers date back to 35 years ago [26, 29, 33]. After that, many dynamic shortest paths algorithms have been proposed (see, e.g., [11, 15, 16, 30, 31, 36]), but their running times in the worst case were comparable to recomputing APSP from scratch.

The first dynamic shortest path algorithms which are provably faster than recomputing APSP from scratch, only worked on graphs with small integer weights. In particular, Ausiello et al. [1] proposed a decrease-only shortest path algorithm for directed graphs having positive integer weights less than C: the amortized running time of their algorithm is O(Cn log n) per edge insertion. Henzinger et al. [21] designed a fully dynamic algorithm for APSP on planar graphs with integer weights, with a running time of O(n4/3 log(nC)) per operation. Fakcharoemphol and Rao in [12] designed a fully dynamic algorithm for single-source shortest paths in planar directed graphs that supports both queries and edge weight updates in O(n4/5 log13/5 n) amortized time per edge operation.

The first big step on general graphs and integer weights was made by King [24], who presented a fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with positive integer weights less than C: the running time of her algorithm is O(n2.5√C log n ) per update.

Demetrescu and Italiano [7] gave the first algorithm for fully dynamic APSP on general directed graphs with real weights assuming that each edge weight can attain a limited number S of different real values throughout the sequence of updates. In particular, the algorithm supports each update in O(n2.5.jS log3 n ) amortized time and each query in O(1) worst-case time. The same authors discovered the first algorithm that solves the fully dynamic all pairs shortest paths problem in its generality [8]. The algorithm maintains ex- plicitly information about shortest paths supporting any edge weight update in O(n2 log3  n)amortized time per operation in directed graphs with non-negative real edge weights. Dis- tance queries are answered with one lookup and actual shortest paths can be reconstructed in optimal time. We note that each update might change a portion of the distance ma- trix as large as Ω(n2). Thus, if the distance matrix has to be maintained explicitly after each update so that queries can be answered with one lookup, O(n2) is the best update bound one could hope for. Other deletions-only algorithms for APSP, in the simpler case of unweighted graphs, are presented in [2].

In this section we consider the dynamic shortest paths algorithm by King [24]. The algorithm is based on the long paths property discussed in Section 36.3.2 and on the reachability tree data structure Section 35.6.

Similarly to the transitive closure algorithms described in Section 36.6 generalized update operations are supported within the same bounds, i.e., insertion (or weight decrease) of a bunch of edges incident to a vertex, and deletion (or weight increase) of any subset of edges in the graph with just one operation.

The main idea of the algorithm is to maintain dynamically all pairs shortest paths up to a distance d, and to recompute longer shortest paths from scratch at each update by stitching together shortest paths of length ≤ d. For the sake of simplicity, we only consider the case of unweighted graphs: an extension to deal with positive integer weights less than C is described in [24].

To maintain shortest paths up to distance d, similarly to the transitive closure algorithm by King described in Section 36.6, the algorithm keeps a pair of in/out shortest paths trees IN (v) and OU T (v) of depth ≤ d rooted at each vertex v. Trees IN (v) and OU T (v) are maintained with the decremental data structure mentioned in Chapter 35.

It is easy to prove that, if the distance dxy between any pair of vertices x and y is at most d, then dxy is equal to the minimum of dxv + dvy over all vertices v such that x ∈ IN (v) and y ∈ OU T (v).

To support updates, insertions of edges around a vertex v are handled by rebuilding only IN (v) and OU T (v), while edge deletions are performed via operations on any trees that contain them. The amortized cost of such updates is O(n2d) per operation.

To maintain shortest paths longer than d, the algorithm exploits the long paths property of Theorem 36.5: in particular, it hinges on the observation that, if H is a random subset of Θ((n log n)/d) vertices in the graph, then the probability of finding more than d consecutive vertices in a path, none of which are from H, is very small. Thus, if we look at vertices in H as “hubs”, then any shortest path from x to y of length ≥ d can be obtained by stitching together shortest subpaths of length ≤ d that first go from x to a vertex in H, then jump between vertices in H, and eventually reach y from a vertex in H. This can be done by first computing shortest paths only between vertices in H using any cubic-time static all-pairs shortest paths algorithm, and then by extending them at both endpoints with shortest paths of length ≤ d to reach all other vertices. This stitching operation requires O(n2|H|) = O((n3 log n)/d) time.

Choosing d = √n log n yields an O(n2.5√log n) amortized update time. As mentioned in Section 36.3.2, since H can be computed deterministically, the algorithm can be derandomized. The interested reader can find further details on the algorithm in [24].

Updates in O(n2 log3 n) Time

In this section we address the algorithm by Demetrescu and Italiano [8], who devised the first deterministic near-quadratic update algorithm for fully dynamic all-pairs shortest paths. This algorithm is also the first solution to the problem in its generality. The algorithm is based on the notions of historical paths and locally historical paths in a graph subject to a sequence of updates, as discussed in Section 36.3.3.

The main idea is to maintain dynamically the locally historical paths of the graph in a data structure. Since by Lemma 36.3 shortest paths are locally historical, this guarantees that information about shortest paths is maintained as well.

To support an edge weight update operation, the algorithm implements the smoothing strategy mentioned in Section 36.3.3 and works in two phases. It first removes from the data structure all maintained paths that contain the updated edge: this is correct since historical shortest paths, in view of their definition, are immediately invalidated as soon as they are touched by an update. This means that also locally historical paths that contain them are invalidated and have to be removed from the data structure. As a second phase, the algorithm runs an all-pairs modification of Dijkstra’s algorithm [9], where at each step a shortest path with minimum weight is extracted from a priority queue and it is combined with existing historical shortest paths to form new locally historical paths. At the end of this phase, paths that become locally historical after the update are correctly inserted in the data structure.

The update algorithm spends constant time for each of the O(zn2) new locally historical path (see Theorem 36.7). Since the smoothing strategy lets z = O(log n) and increases the length of the sequence of updates by an additional O(log n) factor, this yields O(n2 log3 n) amortized time per update. The interested reader can find further details about the algorithm in [8].