Challenge: Bellmann-Ford

In this Challenge Lesson, we’ll implement the Bellmann-Ford algorithm, an alternative algorithm for the SSSP. While it runs slower than Dijkstra, it is able to correctly handle graphs with negative edge weights as long as there are no negative cycles.

The Bellmann-Ford algorithm

The Bellmann-Ford algorithm computes distances by repeatedly relaxing all edges of the graphs. Recall that relaxing an edge $(u,v)$ means checking whether

$$d(u) + w(u, v) < d(v),$$

in which case we can update the tentative distance $d(v)$.

To run Bellmann-Ford from a starting node $u$, we

1. Initialize $d(u) = 0$ and $d(v) = \infty$ for $v \neq u$.
2. Try to relax each edge of the graph.
3. Repeat step (2) until the distance estimates do not change anymore.

Finally, the value of $d(v)$ corresponds to the distance of node $v$ from node $u$. As usual, we can also keep track of predecessor nodes when relaxing edges to construct the shortest paths themselves.

Example execution

Let’s run Bellmann-Ford on this small example graph, starting from node $3$: