Constructing a Distance Sensitivity Oracle in O(n2.5794M) Time

We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in 1, 2, dots, M, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n2.5794M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n2.7233M), and even in the easier case of undirected graphs, the best preprocessing time is O(n2.6865M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo xr. The algorithm is adapted from [Zhou, Labahn, and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in 1, 2, dots, M, in O(n2.5286M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n2.6865M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.