0

Given a graph that has negative weights but we know for sure it has no negative cycle:

Add a big enough constant to all weights so they are now positive and use Dijkstra's algorithm to find the smallest path.

Is the above correct if we don't have negative cycles? If we have negative cycles we can't use that algorithm since it will need to revisit the nodes Dijkstra marked as completed.

MATH000
  • 1,043
  • 3
  • 13
  • 24

1 Answers1

5

By adding a constant to all the weights you shall make paths with more number of edges more costly and paths with less number of edges relatively less costly hence disrupting the original problem.

So you can't apply Dijkstra even if there is no negative weight cycle.

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • Thanks for the reply! If I leave the weights negative but know for sure there won't be a negative cycle, will Dijkstra work? – MATH000 May 16 '16 at 15:46
  • @MATH000 check this link. http://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges – Abhishek Bansal May 16 '16 at 15:47
  • Thanks for the link, but all examples have negative cycles. Can you provide one example where Dijkstra fails in a graph without negative cycle? – MATH000 May 16 '16 at 15:57
  • @MATH000 in the accepted answer, the edges are A->B, A->C and B->C. It is a DAG, hence no cycle. – Abhishek Bansal May 16 '16 at 16:00