Shortest paths disallowing each edge

Question

I'd appreciate any pointers or terms that could get me started in the right direction.

We have a directed graph $G=(V,E)$ and lengths $l_{ij}$ for each edge $ij$ that can be assumed positive. There is a special start node $s$ and end node $t$.

For each edge $ij$, we'd like to compute the length of the shortest path from $s$ to $t$ that does not use edge $ij$.

A simple brute force algorithm is to run a shortest path algorithm for each edge, each time removing a different edge from the original graph. Is there a more efficient algorithm that takes advantage of the fact that there is a lot of repeated computation happening in this brute force algorithm?

Thanks in advance.

Answer 1

The problem you mention is called "replacement paths". Here are a few references:

1. Gotthilf and Lewenstein, Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Proc. Letters, 109(7):352–355, 2009. This paper gives the fastest to date exact algorithm for the replacement paths problem, running in time $O(mn+n^2\log\log n)$ time in graphs with $n$ nodes and $m$ edges.
2. A. Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proc. SODA, pages 742–755, 2010. This paper amazingly gives a quasilinear time approximation scheme for the problem.
3. J. Hershberger, S. Suri, and A. Bhosle. On the difficulty of some shortest path problems. In Proc. STACS, pages 343–354, 2003. This paper shows that any path-comparison algorithm solving the replacement paths problem exactly must take at least $\Omega(m\sqrt{n})$ time.
4. V.Vassilevska W., R. Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In Proc. FOCS, pages 645-654, 2010. We show that if you obtain an $O(n^{3-\varepsilon})$ time exact algorithm for replacement paths for any constant $\varepsilon>0$, then this can be converted to an $O(n^{3-\varepsilon'})$ time algorithm for all pairs shortest paths for constant $\varepsilon'>0$. Such a truly subcubic algorithm for all pairs shortest paths is a longstanding open problem.
5. O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication. In Proc. FOCS, pages 655-662, 2010. and V. Vassilevska W. Faster Replacement Paths. In Proc. SODA, pages 1337-1346, 2011. These papers show how to use fast matrix multiplication to find replacement paths in graphs with integer edge weights in the interval $\{-M,\ldots, M\}$. The latter paper gives the best known runtime so far, $\tilde{O}(Mn^\omega)$.

Answer 2

If you want to associate to each edge the length of a shortest path between $s$ and $t$, you can begin with computing a shortest path in the whole graph, and associate to each edge not in the shortest path you just computed the length of the current shortest path. After that, you have at most $n-1$ edges left for which you do not know the answer.