Shortest paths disallowing each edge 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.
The problem you mention is called "replacement paths".
Here are a few references:


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.
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.
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.
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&gt;0$, then this can be converted to an $O(n^{3-\varepsilon&#39;})$ time algorithm for all pairs shortest paths for constant $\varepsilon&#39;&gt;0$. Such a truly subcubic algorithm for all pairs shortest paths is a longstanding open problem.
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)$.