function bellmanFord(graph: Graph, source: Node) {const distance = new Map(graph.nodes.map((node) => [node, Infinity])); distance.set(source, 0);
for (let round = 1; round < graph.nodes.length; round++) {let changed = false;
for (const edge of graph.edges) {const candidate = distance.get(edge.from)! + edge.weight;
if (candidate >= distance.get(edge.to)!) continue;
distance.set(edge.to, candidate); changed = true;
}
if (!changed) break;
}
for (const edge of graph.edges) if (distance.get(edge.from)! + edge.weight < distance.get(edge.to)!) throw new Error("negative cycle");return distance;
}
Source A gets distance 0, every other node ∞. 6 of the 15 edges are negative: Dijkstra could not be trusted here.
Understanding Bellman-Ford
The idea
Bellman-Ford makes no assumption about the order in which nodes are settled. It simply relaxes every edge, in any order, and repeats: after one full pass every shortest path of one edge is correct, after two passes every path of two edges, and so on. V − 1 passes cover every simple path, so the distances are final.
Because it never commits to a node early, negative edge weights are fine. One extra pass tells whether anything still improves; if it does, a negative cycle is reachable and no shortest path exists. The price is V · E work instead of Dijkstra's E log V.
The four stages
Complexity
Versus its siblings
Pseudocode
BELLMANFORD(graph, source)
dist[source] ← 0; every other dist ← ∞
repeat V − 1 times, or until a round changes nothing
for each edge from → to with weight: if dist[from] + weight < dist[to]: dist[to] ← dist[from] + weight
one more round: if anything still improves, a negative cycle exists
When to use
Pitfalls
History
Alfonso Shimbel described the relaxation scheme in 1955; Lester Ford Jr. published it in 1956 and Richard Bellman in 1958, and Edward Moore independently in 1957, which is why it is sometimes Bellman-Ford-Moore. Its distributed form ran the ARPANET's routing in the 1970s.