Djikstra’s algorithm doesn’t work when there are negative edge weights. To fix this, instead of picking the uu with the smallest d[u]d[u] 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.

The Bellman-Ford algorithm is slower than Dijkstra (nmnm vs nlogn+mn\log n + m 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.

The algorithm

Keep track of an array sequence d(i)d^{(i)} that contains distances for each vertex.

  1. Set d(0)d^{(0)} to be all infinities except for the starting node
  1. For every vertex that has non-infinite value, update its neighbors with the same min-sum algorithm.
  1. Keep on doing this until you have stepped n1n-1 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.

Formal algorithm

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 d(k)[l]d^{(k)}[l] is the minimum weight you need to reach from the source to node ll in at most kk steps. You can show this by induction.

  1. Base case: this is obvious
  1. Inductive case:
    1. A neighbor to ll contains the minimum weight in k1k-1 steps. ll itself contains the minimum weight in k1k-1 steps.
    1. Suppose that n(l)ln(l)→l yields a smaller weight. Then, the new path is kk steps, as desired
    1. Suppose that it does not yield a smaller weight. Then, we keep the old path which is k1kk-1 \leq k as desired.

Therefore, we only need to run the algorithm n1n-1 times. Why? Well, to touch all the nn vertices, we need n1n-1 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 n1n-1 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 nn round and we iterate through mm edges in the round, so the complexity is O(mn)O(mn)