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)

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.