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 of a shortest path from any given vertex x to another given vertex y avoiding an arbitrary 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^2 log n) space, where n is the number of vertices in G. We also show that if we are willing to use Theta(n^2.5) space, we can reduce the preprocessing time by a factor of n^0.5 while maintaining 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.