Motivation

Djikstra’s algorithm doesn’t work when there are negative edge weights. To fix this, instead of picking the $u$ with the smallest $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 ($nm$ vs $n\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)}$ that contains distances for each vertex.

1. Set $d^{(0)}$ to be all infinities except for the starting node

2. For every vertex that has non-infinite value, update its neighbors with the same min-sum algorithm.

3. Keep on doing this until you have stepped $n-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]$ is the minimum weight you need to reach from the source to node $l$ in at most $k$ steps. You can show this by induction.

1. Base case: this is obvious

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

Therefore, we only need to run the algorithm $n-1$ times. Why? Well, to touch all the $n$ vertices, we need $n-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 $n-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.

Complexity

There are $n$ round and we iterate through $m$ edges in the round, so the complexity is $O(mn)$