How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.

  • $\begingroup$ This should be pretty simple. What have you tried? Have you tried solving this for just a small number of nodes? $\endgroup$ – BlueRaja - Danny Pflughoeft Nov 2 '19 at 22:54
  • $\begingroup$ I think if there is a path from u->x->v where x is to be deleted then connecting u->v by d(u,x)+d(x,v) should solve the problem. Actually, I have 2 follow up questions on this but want to solve them by myself so did not post the entire question here. 8th question in excercises if anyone is curious jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf $\endgroup$ – Deep Bodra Nov 2 '19 at 23:09
  • $\begingroup$ You should specify in your question that you're allowed to add/reweigh edges, if that's the case. $\endgroup$ – Steven Nov 2 '19 at 23:13
  • $\begingroup$ @Steven It is not mentioned in the question either. I was learning graph theory and found a bunch of interesting questions. See my previous comment for the link to the original question $\endgroup$ – Deep Bodra Nov 2 '19 at 23:17
  • 1
    $\begingroup$ But it is specified in the question... The source you linked says: "Describe an algorithm that constructs a directed graph $G' = (V \setminus \{v\}, E')$ with weighted edges, such that the shortest-path distance between any two vertices in $G'$ is equal to the shortest-path distance between the same two vertices in $G$, in $O(V^2)$ [sic] time." $\endgroup$ – Steven Nov 2 '19 at 23:20

Your Answer

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

Browse other questions tagged or ask your own question.