Djikstra’s algorithm doesn’t work when there are negative edge weights. To fix this, instead of picking the with the smallest to update, just update everything at once. The reason why this works is that the priority-based selection is what kills the Djikstra approach. We may never explore a path that turns out to be shorter.
Furthermore, if the weights change on the graph, we need to re-run the entire thing.
Bellman-Ford algorithm is slower than Dijkstra ( vs but it can handle negative edge weights and allows for some flexibility if the weights change.
It can also detect negative cycles, which we will see in a second.
Why can’t we just add a constant to the weights
A common question is whether or not you can just add a constant to the weights such that non of the weights are negative anymore. But there are actually some big problems. By adding a constant, you are punishing paths with more edges, and often paths with more edges are the paths that are good when you have negative edges.
Another problem is that you can’t detect/handle negative cycles.
Keep track of an array sequence that contains distances for each vertex.
- Set to be all infinities except for the starting node
- For every vertex that has non-infinite value, update its neighbors with the same min-sum algorithm.
- Keep on doing this until you have stepped times through the array.
As a side note, you don’t need to ignore the infinite valued vertices, but they are not going to change anything for obvious reasons.
Here we see that we don’t need to keep all the past arrays. This saves complexity. We use the list of arrays to better understand the process
Why does it work?
You can show that is the minimum weight you need to reach from the source to node in at most steps. You can show this by induction.
- Base case: this is obvious
- Inductive case:
- A neighbor to contains the minimum weight in steps. itself contains the minimum weight in steps.
- Suppose that yields a smaller weight. Then, the new path is steps, as desired
- Suppose that it does not yield a smaller weight. Then, we keep the old path which is as desired.
Therefore, we only need to run the algorithm times. Why? Well, to touch all the vertices, we need edges. Without negative cycles, the shortest path contains no repeat vertices (simple path).
The bane of negative cycles
Negative cycles means that there is no optimal path because you can just go into the negative cycle and get arbitrarily low values. Djikstra’s algorihtm isn’t robust to this, but Bellman-Ford will be able to detect negative cycles.
Detecting negative cycles
If there is a negative cycle, the optimal path is a cycle. Therefore. the algorithm will not converge after steps. You can detect this by doing one more update and seeing what happens. If things change, you’ve stumbled across a negative cycle.
There are round and we iterate through edges in the round, so the complexity is