<p>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 <em>not in the shortest path you just computed</em> 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.</p>

CC BY-SA 3.0
2011-05-31T22:23:49.083Z
Thank you.  I've accepted the other answer, because it gives more of the context I was looking for, but I will probably use this approach for the first pass implementation that I need.
dan_x
CC BY-SA 3.0
2011-05-31T19:36:26.310Z
2011-05-31T21:31:07.810Z
2011-05-31T21:31:07.810Z
Nathann Cohen
<p>The problem you mention is called "replacement paths".
Here are a few references:</p>

<ol>
<li><em>Gotthilf and Lewenstein, Improved algorithms
for the k simple shortest paths and the
replacement paths problems. Inf. Proc. Letters,
109(7):352–355, 2009.</em> 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.</li>
<li><em>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.</em> This paper amazingly gives a quasilinear time approximation scheme for the problem.</li>
<li><em>J. Hershberger, S. Suri, and A. Bhosle. On the
difficulty of some shortest path problems. In Proc.
STACS, pages 343–354, 2003.</em> This paper shows that any <em>path-comparison</em> algorithm solving the replacement paths problem exactly must take at least $\Omega(m\sqrt{n})$ time.</li>
<li><em>V.Vassilevska W., R. Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In Proc. FOCS, pages 645-654, 2010.</em> 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.</li>
<li><em>O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication. In Proc. FOCS, pages 655-662, 2010.</em> and <em>V. Vassilevska W. Faster Replacement Paths. In Proc. SODA, pages 1337-1346, 2011.</em> 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)$.</li>
</ol>

CC BY-SA 3.0
2011-05-31T21:35:07.317Z
2011-05-31T21:35:07.317Z
virgi
<p>I'd appreciate any pointers or terms that could get me started in the right direction.</p>

<p>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$.</p>

<p>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$.</p>

<p>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?</p>

<p>Thanks in advance.</p>

<ds.algorithms><reference-request><graph-algorithms>
Shortest paths disallowing each edge
dan_x
# Shortest paths disallowing each edge

(Asked by: username_0 on 2011-05-31)

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.

**Tags:** ds.algorithms, reference-request, graph-algorithms

---

## 2 answers

### Answer by username_2 on 2011-05-31. Score: 18 | Accepted answer

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 by username_1 on 2011-05-31. Score: 8

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.

> **Comments:**
> **username_0**: Thank you.  I've accepted the other answer, because it gives more of the context I was looking for, but I will probably use this approach for the first pass implementation that I need.  

---

