| 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²log n) space, where n is the number of vertices in G. We also show that if we are willing to use Θ(n²√n) space, we can reduce the preprocessing time by a factor of √n 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. |