Question

a) Sam sees that he has a graph with negative weight edges and wants to find a shortest path tree from a given source vertex. He determines that the smallest edge weight in the graph is -10, so he just adds 11 to every edge weight, then runs Dijkstra’s on the new graph. Is the shortest path tree he finds the same as the shortest path tree in the original graph? Explain why or why not. Note that by “the same” we mean, does it necessarily contain the same vertices and the same edges?

Answer 1

This would not work:

A counterexample would be:

consider a graph on three vertices G={A,B,C}

add edges A-B with weight 5

add edge A-C with edge weight 2

and add edge B-C with weight -10

    

in this graph the shortest path discovered from A to C would be A-B-C with cost 5+(-10)=-5.

after adding 11 to each edge G becomes,

Now the shortest path by dijkistra algorithm from A to C would be along edge A-C with weight 13.

So the paths are not same.