CODEWITHSUNDEEP
algorithmdijkstra
Night Shade
Night Shade

Reputation: 78

Does Dijkstra work with all negative weights

Would Dijkstra work with all negative weights, considering the condition, that we choose the most negative value and go ahead with it? [Normal Dijkstra Algorithm]

I couldn't find the answer online.

Thank you.

Upvotes: 0

Views: 146

Answers (1)

John Kugelman
John Kugelman

Reputation: 361585

If all the weights were negative and you chose the least negative weights that'd be isometric traditional Dijkstra's where weights are positive and the least positive weights are chosen, and hence would work fine. To say it another way, you'd want to pick the maximum weights (least negative).

Choosing the most negative weight is like choosing the most positive weight. It doesn't work since Dijkstra's is a minimization algorithm.

Dijkstra's also fails when you have a mix of positive and negative weights and the graph has cycles. If the goal were to maximize total weight then a cycle with negative weight would be fine, but one with positive weight would lead to an endless loop where the algorithm chooses to take the cycle over and over and over.

Upvotes: 2

Related Questions