Destroy shortest path in graph

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)

• Are all the edge lengths 1? – Peter Shor May 25 '14 at 23:22
• @PeterShor yes. – amineh May 26 '14 at 4:24
• Please check tour and help center. This question seems more suitable for Computer Science which has a broader scope. – Kaveh May 30 '14 at 20:24

1 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'$.

• this algorithm eliminate all edges in shortest path but question want minimum number of edges that if removed the shortest path become longer. – amineh May 26 '14 at 6:39
• @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 May 26 '14 at 8:44
• @amineh - see my revised answer, the minimal cut is exactly what you're looking for, the proof is easy as well. – R B May 26 '14 at 8:51