Nptel Assignment Question

Question

Consider the following strategy to convert a graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be -k. Then, for each edge in the graph with weight w, update the weight to w+k+1. Consider the following claim:

• To solve the shortest path problem in the original graph, we can run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances.

Which of the following is not correct.

• A. The claim is not true in general.
• B. The claim is true for all graphs.
• C. The claim is true for connected acyclic graphs.
• D. The claim is not true in general for connected graphs with cycles

Answer 1

The claim is not true in general. Option(A)

Consider the graph with nodes A,B,C and A->B, A->C, B->C with weights 1,1,-1 in that order. The shortest path from A to C is A->B->C with weight 0. Your strategy adds two to all weights, making A->C shorter (weight 3).