Algorithms

Dijkstras algorithm does not generally work for graphs with negative weights. Consider the following modi?cation: determine the lowest weight wmin of any edge in the graph, add the absolute value of that weight |wmin| to all edges weights, then run Dijkstra, and ?nally subtract |wmin| again to adjust the weights of the computed shortest paths. Show that this modi?cation does not work. Give an example of a graph G for which this modi?ed version of Dijkstras algorithm computes at least one incorrect shortest path and point out a pair of vertices along with the incorrectly computed path and a correct path.