Bellman-Ford for Negative Weights

The Bellman-Ford algorithm computes single-source shortest paths in a directed graph that may contain negative edge weights.

Dijkstra's algorithm fails on negative edges because its greedy strategy permanently finalizes the closest unvisited vertex. Once a vertex is finalized, a later negative edge that would shorten its distance is never considered. Bellman-Ford avoids this by never committing: it repeatedly improves a running estimate $d[v]$ of the shortest-path distance from the source $s$ to each vertex $v$.

Initialize

$$d[s] = 0, \qquad d[v] = \infty \text{ for all } v \ne s.$$

The edge relaxation of a directed edge $(u, v)$ with weight $w(u, v)$ is the test

$$\text{if } d[u] + w(u, v) < d[v], \text{ then } d[v] \leftarrow d[u] + w(u, v).$$

For example, suppose at some point $d[u] = 3$, $d[v] = 10$, and $w(u, v) = -5$. We compute the candidate distance

$$d[u] + w(u, v) = 3 + (-5) = -2.$$

Since $-2 < 10$, the test succeeds and we update $d[v] \leftarrow -2$. If $d[v]$ had instead been $-7$, the candidate $-2$ would not beat $-7$ and we would leave $d[v]$ unchanged.