[[the-dijkstra|Dijkstra]] is fast but breaks when edges can be NEGATIVE. Bellman-Ford is the sturdy alternative: just relax every edge over and over — V−1 sweeps — and the shortest distances settle out, negatives and all. One more sweep that still improves something? Then a negative cycle exists (free money forever), and it says so. It’s slower but honest, and it powers internet routing. Slide through the relaxation sweeps.
Bellman–Ford computes single-source shortest paths by RELAXATION: repeat V−1 times, and for every edge (u,v,w) set dist[v]=min(dist[v], dist[u]+w). After V−1 sweeps every shortest path (at most V−1 edges) has settled. Unlike [[the-dijkstra|Dijkstra]] it tolerates NEGATIVE edge weights, and a Vth sweep that still relaxes an edge PROVES a negative-weight cycle is reachable (no finite shortest path). It costs O(V·E) — slower than Dijkstra’s O(E log V) — and underlies distance-vector routing (RIP) and arbitrage detection. A fail-loud self-check throws unless it finds the known distances on a graph with a negative edge and reports no false cycle. ◆ real graph algorithms, node-verified.
O(V·E) is slower than Dijkstra; use it only when negatives are possible. The relaxation result and the negative-cycle certificate are exact.