摘要：We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, ⦠, M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x â^^ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with OÌf(n^2.7233 M²) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to OÌf(n^2.6865 M²). Our algorithms are randomized with correct probability ⥠1-1/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with OÌf(n^2.8729 M) preprocessing time and polylog(n) query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+OÌf(Mn²)â<. Q and query time O(1). (Here OÌf(â<.) hides polylog(n) factors.)
