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 Θ (n ^2.5) space, we can improve the preprocessing time to O(mn ^1.5 + n^2.5 log 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.