Oracles for Distances Avoiding a Failed Node or Link
Camil Demetrescu, Mikkel Thorup, Rezaul Chowdhury, Vijaya Ramachandran · SIAM Journal on Computing · 2008
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^2\log n)$ space, where n is the number of vertices in G. The construction time for our oracle is $O(mn^{2} + n^{3}\log n)$. However, if one is willing to settle for $\Theta (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.