CODEWITHSUNDEEP
algorithmgraphshortest-pathdijkstra
Pradhan
Pradhan

Reputation: 421

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

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.

Upvotes: 4

Views: 1417

Answers (1)

Nayuki
Nayuki

Reputation: 18552

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.

Example graph

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

Upvotes: 17

Related Questions