Bellman-Ford Algorithm is a dynamic programming problem that solves single-source shortest path.
d[v] = \infty
d[s] = 0
for i = 0, ..., n-2:
for v in v:
d_prev = d
for u in v.in_neigbors:
d[v] = min(d_prev[v], d_prev[u] + w(u,v))
Notice you need \(O\qty(n)\) space (2 \(d\) rounds, the previous round and the next round), and runtime is \(O\qty(nm)\) (outer \(n\) loop, inner is an iteration between \(deg\qty(v)*|v| = |e| = m\); that is, we have an minimum over the degree of each \(v\) for every \(v\), which adds up to the total number of edges.)
\(d^{(i)}[v]\) is the cost of the shortest path between \(s\) and \(v\) with at most \(i\) edges (i.e. we propagate “one edge of minimum” forward each time).
So \(d^{(n-1)}[v]\) is the cost of the shortest path between \(s\) and \(v\) if there are no negative cycles.
- if there are no negative cycle, after n iterations, the distance estimates will stop changing
- if there is a negative cycle, then the distances will keep updating
…so you can just run one more iteration of Bellman-Ford Algorithm to check for negative cycles.