Shortest paths disallowing each edge
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)$.