# Remove a vertex from a graph keeping shortest path distance same

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.

• This should be pretty simple. What have you tried? Have you tried solving this for just a small number of nodes? – BlueRaja - Danny Pflughoeft Nov 2 '19 at 22:54
• 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 – Deep Bodra Nov 2 '19 at 23:09
• You should specify in your question that you're allowed to add/reweigh edges, if that's the case. – Steven Nov 2 '19 at 23:13
• @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 – Deep Bodra Nov 2 '19 at 23:17
• 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." – Steven Nov 2 '19 at 23:20