Bellman-Ford
Single-source shortest paths that handles negative edge weights.
How it works
The Bellman-Ford algorithm finds the shortest path from a single source to all other nodes in a weighted, directed graph, and crucially handles negative edge weights that would break Dijkstra's greedy approach. It works by performing V−1 passes over all edges, relaxing each one — if the path through edge u→v is cheaper than the current known distance to v, that distance is updated. After V−1 passes, the shortest distances are guaranteed to be correct for any graph without negative cycles.
Unlike Dijkstra's algorithm, which processes nodes in order of distance using a priority queue, Bellman-Ford processes every edge on every pass regardless of order. This brute-force style makes it slower — O(VE) versus Dijkstra's O((V+E) log V) — but it's the correct choice whenever negative weights are present. It also has the ability to detect negative-weight cycles: if any distance still improves on an extra (V-th) pass, a negative cycle exists.
The algorithm is a classic example of dynamic programming on graphs: the invariant after pass k is that dist[v] holds the shortest path to v using at most k edges. Each pass extends this guarantee by one hop, and since any simple path has at most V−1 edges, V−1 passes suffice for correctness.
Complexity
Visualizer
Where it's used in the real world
RIP (Routing Information Protocol)
Distance-vector routing in network routers handles negative metricsRIP uses a Bellman-Ford variant distributed across routers where each node exchanges distance vectors with neighbors. Unlike link-state protocols (which run Dijkstra centrally), each router independently relaxes routes hop-by-hop, making Bellman-Ford a natural fit for the decentralized update model.
Currency arbitrage detection
Detecting negative cycles in currency exchange rate graphsBy taking the negative logarithm of exchange rates as edge weights, a negative cycle in the graph represents an arbitrage opportunity — a sequence of trades that yields profit. Bellman-Ford's ability to detect negative cycles makes it the standard algorithm for this problem in quantitative finance.
Traffic engineering with penalties
Road networks with toll credits (negative weights)Some routing systems model road segments with variable costs that include credits, subsidies, or incentives — effectively creating negative-weight edges. Bellman-Ford correctly handles such models, finding the truly cheapest route even when some segments have negative net cost.
Implementation
function bellmanFord(
nodes: string[],
edges: { from: string; to: string; weight: number }[],
start: string,
end: string
): { dist: number; path: string[] } | null {
const INF = Infinity;
const dist: Record<string, number> = Object.fromEntries(nodes.map(n => [n, INF]));
const parent: Record<string, string | null> = Object.fromEntries(nodes.map(n => [n, null]));
dist[start] = 0;
const n = nodes.length;
// V-1 relaxation passes
for (let pass = 0; pass < n - 1; pass++) {
let updated = false;
for (const { from: u, to: v, weight: w } of edges) {
if (dist[u] !== INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = u;
updated = true;
}
}
if (!updated) break; // early exit if no changes
}
// Check for negative cycles (optional V-th pass)
for (const { from: u, to: v, weight: w } of edges) {
if (dist[u] !== INF && dist[u] + w < dist[v]) {
throw new Error("Graph contains a negative-weight cycle");
}
}
if (dist[end] === INF) return null;
// Reconstruct path
const path: string[] = [];
for (let cur: string | null = end; cur !== null; cur = parent[cur]) {
path.unshift(cur);
}
return { dist: dist[end], path };
}