Can we use Dijkstra's to find the shortest path even in a graph having negative edge weights?

Question

Suppose I have a graph where the minimum edge weight is −100. Can I add 100 as an offset to all the edges and use Dijkstra's algorithm?

Please help me understand why such a method gives wrong solution.

Answer 1

Adding 100 to every edge weight gives the wrong solution because it penalizes paths that have more edges than paths that have fewer edges.

For example, suppose we have a graph, and the shortest path from point A to point B has 3 edges and a total distance 5. Suppose some other path from point A to point B has 2 edges but a total distance of 10.

If we add 100 to each edge weight, then the first path has a cost of 305, while the second path has a cost of 210. So the second path becomes shorter than the first path.

Therefore, we can conclude that adding an offset or bias to each edge weight does not necessarily preserve shortest paths.