Bellman-Ford
Try every edge, and keep any route it shortens. Do that V − 1 times. Any shortest route uses at most V − 1 edges, so by the end every one has been found, negative edges included. If a further pass still shortens something, a negative cycle exists.
Find the shortest route from A to every node. Some edges here have negative lengths.
1function bellmanFord(edges, n, start) {2 const dist = new Array(n).fill(Infinity);3 dist[start] = 0;4 for (let round = 1; round < n; round++) {5 for (const [u, v, w] of edges) {6 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;7 }8 }9 for (const [u, v, w] of edges) {10 if (dist[u] + w < dist[v]) return null;11 }12 return dist;13}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V · E | the code always runs all V − 1 rounds |
| average | V · E | an early stop helps when a round changes nothing |
| worst | V · E | much slower than Dijkstra on big graphs |
| space | V | one distance per node |
Where it breaks
- Where Dijkstra goes wrong. Pick Negative edge: A to B directly is 4, but A to C to B is 5 − 3 = 2. Dijkstra settles B at 4 before ever looking through C. Bellman-Ford keeps checking and finds 2.
- Negative cycles have no answer. Pick Negative cycle: going round B, C, D lowers the total by 2 each time, so there is no shortest route. The extra pass at the end is how the algorithm notices.
- It is slow. V − 1 full passes over every edge is far more work than Dijkstra. Use it only when weights can really be negative, as with currency exchange rates or costs that can turn into gains.