Suggest edit — Bellman-Ford Algorithm

Title

Name

Note

---
title: "Bellman-Ford Algorithm"
type: concept
related: [Bellman Ford Algorithm]
source: https://www.jemoka.com/posts/kbhbellman_ford_algorithm/
confidence: high
status: active
---

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 &ldquo;one edge of minimum&rdquo; 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 &hellip;so you can just run one more iteration of Bellman-Ford Algorithm to check for negative cycles.