Oracles for Distances Avoiding a Failed Node or Link

We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length and first hop of a shortest path from any given vertex x to any given vertex y avoiding any given vertex or edge. As a natural application, this problem models routing in networks subject to node or link failures. We describe a deterministic oracle with constant query time for this problem that uses O(n²log n) space, where n is the number of vertices in G. The construction time for our oracle is O(mn² + n³log n). However, if one is willing to settle for Θ (n2.5) space, we can improve the preprocessing time to O(mn1.5+n2.5log n) while maintaining the constant query time. Our algorithms can find the shortest path avoiding a failed node or link in time proportional to the length of the path.