What is Bellman-Ford?
Bellman-Ford finds the cheapest cost from one starting point to every other point in a graph, even when some
edges are negative. It does this by relaxing every edge in the graph, over and over, exactly
V - 1 times — where V is the number of vertices.
- Relax
- Check if going through this edge beats the best cost found so far, and update it if it does
- Pass
- One full sweep over every edge in the graph, relaxing each one once
- Negative cycle
- A loop of edges whose total cost is negative, so walking it again and again keeps lowering the cost
Why Bellman-Ford at all?
Picture prices between towns, and you're standing in town A asking the same question over and over: "can any of my current best prices to each town still be beaten by going through some other town?"
Dijkstra asks that question too, but it assumes prices only go up as you travel, so it can commit to an answer the moment it sees a town and never revisit it. Bellman-Ford makes no such assumption — it just keeps asking, edge by edge, until nothing changes.
Every relax either lowers a price or leaves it alone — it never makes one worse.
What does the algorithm actually do?
Two things, and almost every Bellman-Ford problem is one of them: relaxing every edge enough times to guarantee an answer, or using one extra pass to catch a graph that has no answer at all.
Relax every edge, V − 1 times
A shortest path can never use more than V - 1 edges without repeating a vertex, so
V - 1 full passes over every edge is always enough for every real shortest path to settle.
If a pass changes nothing, the answer already converged and you can stop early.
A pass that changes nothing means every shortest path has already been found.
Detect a negative cycle with one extra pass
Run the usual V - 1 passes, then run one more. If that extra pass can still relax an
edge, some path kept getting cheaper past the point where every real shortest path should have
settled — which only happens if a negative-weight cycle feeds into it.
A change on the "extra" pass is the tell — the cycle keeps paying you to loop it again.
Two passes, one algorithm
Underneath, Bellman-Ford is two small loops stacked on top of each other: a relaxation loop that finds the distances, and an optional extra pass that checks whether those distances can be trusted.
The relaxation loop
For V - 1 passes, walk every edge (u, v, w) and ask whether
dist[u + w] beats dist[v]. If it does, that's a cheaper route to v — take it.
Each relax only ever looks at one edge and its two endpoints.
function bellmanFord(n: number, edges: number[][], src: number): number[] {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (let i = 0; i < n - 1; i++) {
let changed = false;
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
changed = true;
}
}
if (!changed) break; // converged early
}
return dist;
}
The negative-cycle check
Run one more pass over every edge after the loop above finishes. Any edge that can still relax means a negative-weight cycle is reachable from the source, and "shortest path" no longer has an answer.
One more improvement after the loop should have finished is the signal.
function hasNegativeCycle(n: number, edges: number[][], src: number): boolean {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
for (let i = 0; i < n - 1; i++) {
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
return true; // still improving past V - 1 passes
}
}
return false;
}
Where it works — and where it breaks
Bellman-Ford's whole reason to exist is negative edges — Dijkstra can't be trusted with them. But Bellman-Ford has its own limit: it only works when "shortest path" actually means something.
Works with negative edges, no cycle
As long as no negative cycle is reachable from the source, relaxing every edge V - 1 times finds
the true shortest paths — negative edges included. That's exactly what Dijkstra can't guarantee.
Breaks when a negative cycle is reachable
If a negative cycle sits on the way, there's no shortest path to find — looping the cycle again and again keeps lowering the cost with no floor. Bellman-Ford's job then is to say so, not to keep relaxing.