Oracles for distances avoiding a link-failure
Camil Demetrescu, Mikkel Thorup · 2002
For a directed graph G we consider queries of the form: "What is the shortest path distance from vertex x to vertex y in G avoiding a failed link (u,v), and what edge leaving x should we use to get on a such a shortest path?" We show that an oracle for such queries can be stored in O(n 2 logn) space with a query time of O(logn). No non-trivial solution was known for this problem.