graphshortest-path

Dijkstra for negative weighted cycles- Add a very large number, make all edges positive

I think the title sufficiently explains what I am trying to ask.

I understand dijkstra is greedy and why it doesn't work on negative weighted cycles(countless questions on overflow).

SO now why don't we add some constant large number to all edges in the graph, so that all the edges are now strictly positive. Now dijkstra should not have any problem in finding the shortest path right?

Even the total path weight can be written as:

Total path weight = New graph path weight - (Fixed large number * path length)

I am missing something here, What is it?

Solution

  • This will find the path with the least number of edges, not the path with the lowest total weight.