<p>Run BFS from $A$, and generate a graph $G'=(V,E')$ that consists only of the edges that are on some shortest path from $A$ to $B$ (i.e. $(x,y)\in E'$ iff $d(a,y)=d(a,x)+1$).</p>

<p>And your answer is the minimal $A-B$ cut in $G'$.</p>

CC BY-SA 3.0
2014-05-26T06:39:53.733Z
this algorithm eliminate all edges in shortest path but question want minimum number of edges that if removed the shortest path become longer.
amineh
CC BY-SA 3.0
2014-05-26T08:44:43.500Z
@R B-do you mean that for removing all shortest path we must remove $i$th  edge of the path? is it the least number of such edges?
amineh
CC BY-SA 3.0
2014-05-26T08:51:11.280Z
@amineh - see my revised answer, the minimal cut is exactly what you're looking for, the proof is easy as well.
R B
CC BY-SA 3.0
2014-05-26T05:49:54.030Z
2014-05-26T08:42:14.900Z
2014-05-26T08:42:14.900Z
R B
<p>Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)</p>

CC BY-SA 3.0
2014-05-25T23:22:48.327Z
Are all the edge lengths 1?
Peter Shor 
CC BY-SA 3.0
2014-05-26T04:24:58.753Z
@PeterShor yes.
amineh
CC BY-SA 3.0
2014-05-30T20:24:13.130Z
Please check [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.
Kaveh
<graph-theory>
Destroy shortest path in graph
amineh
# Destroy shortest path in graph

(Asked by: username_0 on 2014-05-25)

Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)

**Tags:** graph-theory
> **Comments:**
> **username_1**: Are all the edge lengths 1?  
> **username_0**: @PeterShor yes.  
> **username_2**: Please check [about] and [help/on-topic]. This question seems more suitable for [cs.se] which has a broader scope.  

---

## 1 answers

### Answer by username_3 on 2014-05-26. Score: 1 | Accepted answer

Run BFS from $A$, and generate a graph $G'=(V,E')$ that consists only of the edges that are on some shortest path from $A$ to $B$ (i.e. $(x,y)\in E'$ iff $d(a,y)=d(a,x)+1$).

And your answer is the minimal $A-B$ cut in $G'$.

> **Comments:**
> **username_0**: this algorithm eliminate all edges in shortest path but question want minimum number of edges that if removed the shortest path become longer.  
> **username_0**: @R B-do you mean that for removing all shortest path we must remove $i$th  edge of the path? is it the least number of such edges?  
> **username_3**: @amineh - see my revised answer, the minimal cut is exactly what you're looking for, the proof is easy as well.  

---

