A nearly optimal oracle for avoiding failed vertices and edges

We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The previous best algorithm produces an oracle of size Õ(n²) that has an O(1) query time, and an Õ(n²√m) construction time. It was a randomized Monte Carlo algorithm that worked with high probability. Our oracle also has a constant query time and an Õ(n²) space requirement, but it has an improved construction time of Õ(mn), and it is deterministic. Note that O(1) query, O(n²) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.