Bellman–Ford algorithm

Remarks

Example: take $V = \set{s, a, b}$ with $w(s, a) = 4$, $w(s, b) = 1$ and $w(b, a) = -2$. After the first round, if the edges are scanned in the order $(s, a), (s, b), (b, a)$, one has $d(s) = 0$, $d(b) = 1$ and $d(a) = -1$. The check in step 3 reports nothing, so the shortest distance from $s$ to $a$ is $-1$.

Non-example of the conclusion: if the edges $a \to b$ of weight $1$ and $b \to a$ of weight $-2$ form a cycle reachable from $s$, the cycle has weight $-1$. Going around it lowers the weight without bound, so no shortest walk exists, and step 3 reports the cycle.

The correctness rests on the fact that after $k$ rounds, $d(v)$ is at most the least weight of a walk from $s$ to $v$ with at most $k$ edges. The running time is $O(nm)$, where $m = \abs{E}$.