can we run Dijkstra's algorithm on the modified graph and subtract the added weights to get the original distances?

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

The claim is not true in general

The claim is true for all graphs

The claim is true for connected acyclic graphs

The claim is not true in general for connected graphs with cycles.


ANSWERS:


Not true in general: Consider the graph with nodes A,B,C and arcs 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).



 MORE:


 ? Dijkstra's Algorithms and Negative Weights and Cycle
 ? Difference constraints on Bellman-Ford algorithm
 ? Difference constraints on Bellman-Ford algorithm
 ? Difference constraints on Bellman-Ford algorithm
 ? Shortest Paths in undirected cyclic graphs
 ? Shortest Paths in undirected cyclic graphs
 ? Shortest Paths in undirected cyclic graphs
 ? Cycles in an Undirected Graph
 ? Finding a pair of edge disjoint paths in a graph, such that the lengths of each one of the paths is smaller than a given constant
 ? Minimum path in an undirected graph with locked and unlocked edges