4 ms·
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 perspect
by 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 agoI 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 agoNit: 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 -----/