23 ms·

Wouldn't a negative cycle be a good thing? You could drive the total cost down as low as you want before exiting the loop.

londons_explore 4y ago
Yes, but the 'lowest' cost path is then travel to cycle, go round loop infinity times, and then go to destination.
vecter 4y ago
Negative cycles are bad for the exact reason you said. Not "bad" from the perspective of "let's lower the cost as much as possible", but "bad" from the perspective that it violates certain assumptions of Dikjstra's algorithm which leads it to produce incorrect results. When have a negative weight cycle, you can drive down the cost to be arbitrarily low by running through that cycle as many times as you'd like. What does "shortest path" or "lowest cost path" mean in this context then? More info: https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges https://stackoverflow.com/questions/13159337/why-doesnt-dijk...
- sitkack 4y ago
  I have seen this in video games where there is some resource that respawns too quickly and the players just end up cycling back to the powerup every n-seconds. Easy to get stuck in a local minimum.
- tylerhou 4y ago
  Nit: It's not negative weight cycles that mess up Dijkstra's, it's negative weights in general. Dijkstra's is effectively a greedy algorithm for finding shortest paths. By their very nature greedy algorithms cannot "look ahead." If there is a negative weight edge locked behind a expensive edge, Dijkstra's won't be able to see the negative weight edge until it's too late. 10 A -----------------> C \ ^ \ 11 -15 / \-----> B -----/
kzrdude 4y ago
It creates a new situation you'll have to handle. If it's assumed the shortest path is finite, how many steps should it maximally take, etc? In many problem settings a negative cycle would indicate the model is broken, and you'd want to know that.

londons_explore 4y ago

Yes, but the 'lowest' cost path is then travel to cycle, go round loop infinity times, and then go to destination.

vecter 4y ago

Negative cycles are bad for the exact reason you said. Not "bad" from the perspective of "let's lower the cost as much as possible", but "bad" from the perspective that it violates certain assumptions of Dikjstra's algorithm which leads it to produce incorrect results. When have a negative weight cycle, you can drive down the cost to be arbitrarily low by running through that cycle as many times as you'd like. What does "shortest path" or "lowest cost path" mean in this context then? More info: https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges https://stackoverflow.com/questions/13159337/why-doesnt-dijk...

sitkack 4y ago
I have seen this in video games where there is some resource that respawns too quickly and the players just end up cycling back to the powerup every n-seconds. Easy to get stuck in a local minimum.
tylerhou 4y ago
Nit: It's not negative weight cycles that mess up Dijkstra's, it's negative weights in general. Dijkstra's is effectively a greedy algorithm for finding shortest paths. By their very nature greedy algorithms cannot "look ahead." If there is a negative weight edge locked behind a expensive edge, Dijkstra's won't be able to see the negative weight edge until it's too late. 10 A -----------------> C \ ^ \ 11 -15 / \-----> B -----/

kzrdude 4y ago

It creates a new situation you'll have to handle. If it's assumed the shortest path is finite, how many steps should it maximally take, etc? In many problem settings a negative cycle would indicate the model is broken, and you'd want to know that.