Pattern Guide
Bellman-Ford & Negative Cycles
"Shortest paths with negative edges. Detect negative cycles. SPFA optimization."
Bellman-Ford finds shortest paths from a source in O(VE), handling negative edge weights unlike Dijkstra. After V-1 relaxation rounds, one more round that still improves distances reveals a negative cycle. SPFA (Shortest Path Faster Algorithm) is a queue-based optimization that is faster in practice. Applications: arbitrage detection, constraint satisfaction (difference constraints).
Problems you can solve with this pattern
4 problems · click any to start solving
// Bellman-Ford — O(VE)
function bellmanFord(n, edges, src) {
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;
}
}
// Detect negative cycle
for (const [u, v, w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v])
return null; // negative cycle
return dist;
}
// SPFA — O(VE) worst case, O(E) average
function spfa(n, adj, src) {
const dist = new Array(n).fill(Infinity);
const inQueue = new Array(n).fill(false);
dist[src] = 0;
const queue = [src];
inQueue[src] = true;
while (queue.length) {
const u = queue.shift();
inQueue[u] = false;
for (const [v, w] of (adj[u] || [])) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) { queue.push(v); inQueue[v] = true; }
}
}
}
return dist;
}Bellman-Ford: V-1 rounds of relaxing all edges. Each round: for each edge (u,v,w), if dist[u]+w < dist[v], update dist[v]. After V-1 rounds, shortest paths are correct (no path has more than V-1 edges). Round V: if any dist still updates, negative cycle exists. SPFA: only re-relax neighbors of updated vertices (BFS-like queue).
// Bellman-Ford — O(VE)
function bellmanFord(n, edges, src) {
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;
}
}
// Detect negative cycle
for (const [u, v, w] of edges)
if (dist[u] !== Infinity && dist[u] + w < dist[v])
return null; // negative cycle
return dist;
}
// SPFA — O(VE) worst case, O(E) average
function spfa(n, adj, src) {
const dist = new Array(n).fill(Infinity);
const inQueue = new Array(n).fill(false);
dist[src] = 0;
const queue = [src];
inQueue[src] = true;
while (queue.length) {
const u = queue.shift();
inQueue[u] = false;
for (const [v, w] of (adj[u] || [])) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) { queue.push(v); inQueue[v] = true; }
}
}
}
return dist;
}- Dijkstra: O(E log V), requires non-negative weights
- Bellman-Ford: O(VE), handles negative weights, detects negative cycles
- SPFA: Bellman-Ford with queue optimization, O(E) average but O(VE) worst
Negative cycle detection: Run one extra round after V-1 rounds. If any distance still decreases, a negative cycle is reachable from the source.
K-hop variant: Run exactly k rounds of relaxation (don't let updates from the same round cascade). Use a copy of the distance array each round.