CODEWITHSUNDEEP
algorithmgraphcomputer-science
MATH000
MATH000

Reputation: 1103

Can we use Dijkstra in this case?

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.

Upvotes: 0

Views: 103

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

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.

Upvotes: 5

Related Questions