Bellman-Ford Algorithm — Shortest Paths with Negative Weights

Dijkstra's algorithm is faster and what you'll use 90% of the time. But it has a hard requirement: no negative edge weights. The moment your graph has a negative edge, Dijkstra can produce wrong answers because its greedy assumption — "once a node is finalized, we've found its shortest path" — breaks down.

Bellman-Ford handles negative weights correctly. It also detects negative cycles (cycles whose total weight is negative), which is something Dijkstra can't even conceptualize. The tradeoff is speed: O(VE) instead of O((V + E) log V).

When You Actually Need Bellman-Ford

• Currency exchange arbitrage detection (negative cycle = free money)
• Network routing protocols (some use distance-vector routing based on Bellman-Ford)
• Any graph where weights represent costs, penalties, or changes that can be negative
• Problems asking you to detect negative cycles
• Shortest paths with at most K edges (a variant of the core algorithm)

If all weights are non-negative, use Dijkstra. Don't reach for Bellman-Ford out of habit.

The Algorithm

Core idea: relax every edge, V-1 times. "Relaxation" means: if going through edge (u, v) gives a shorter path to v, update v's distance.

Why V-1 iterations? The shortest path between any two vertices has at most V-1 edges (in a graph with no negative cycles). Each iteration propagates shortest-path information one edge further. After V-1 iterations, all shortest paths are found.

Python

def bellman_ford(n, edges, source):
    """
    n: number of vertices (0 to n-1)
    edges: list of (u, v, weight)
    source: starting vertex
    Returns: distance array, or None if negative cycle exists
    """
    dist = [float('inf')] * n
    dist[source] = 0

# relax all edges V-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

# check for negative cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle detected

return dist

JavaScript

function bellmanFord(n, edges, source) {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

// relax all edges V-1 times
  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;
      }
    }
  }

// check for negative cycles
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // negative cycle
    }
  }

return dist;
}

Step-by-Step Example

Graph with 5 vertices, edges: (0,1,6), (0,2,7), (1,2,8), (1,3,5), (1,4,-4), (2,3,-3), (2,4,9), (3,1,-2), (4,0,2), (4,3,7)

Source: vertex 0.

Iteration	dist[0]	dist[1]	dist[2]	dist[3]	dist[4]
Init	0	∞	∞	∞	∞
1	0	6	7	4	2
2	0	2	7	4	-2
3	0	2	7	4	-2
4	0	2	7	4	-2

After iteration 2, values stabilize. Iterations 3 and 4 make no changes. That's normal — the algorithm often converges before V-1 iterations.

You can add an early termination check: if no distance was updated in an iteration, stop early. Doesn't change worst-case complexity but speeds things up in practice.

Negative Cycle Detection

After V-1 relaxation rounds, all shortest paths should be finalized. Do one more round. If any distance still decreases, it means a path keeps getting shorter indefinitely — a negative cycle.

def has_negative_cycle(n, edges):
    dist = [0] * n  # start all at 0 to detect any negative cycle

for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True

return False

Notice the different initialization: dist = [0] * n instead of infinity. Starting from a single source only detects negative cycles reachable from that source. Starting all at 0 simulates a virtual source connected to all vertices with 0-weight edges — catching negative cycles anywhere in the graph.

Variant: Shortest Path with At Most K Edges

"Find the cheapest flights within K stops." This is LeetCode 787, and it's Bellman-Ford with a twist: instead of V-1 iterations, do exactly K+1 iterations (K stops = K+1 edges).

The critical change: use the distances from the previous iteration, not the current one. Otherwise, you might use a path with more edges than allowed.

def cheapest_flights(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0

for _ in range(k + 1):
        prev = dist[:]  # copy previous iteration's distances
        for u, v, w in flights:
            if prev[u] != float('inf') and prev[u] + w < dist[v]:
                dist[v] = prev[u] + w

return dist[dst] if dist[dst] != float('inf') else -1

function cheapestFlights(n, flights, src, dst, k) {
  let dist = new Array(n).fill(Infinity);
  dist[src] = 0;

for (let i = 0; i <= k; i++) {
    const prev = [...dist];
    for (const [u, v, w] of flights) {
      if (prev[u] !== Infinity && prev[u] + w < dist[v]) {
        dist[v] = prev[u] + w;
      }
    }
  }

return dist[dst] === Infinity ? -1 : dist[dst];
}

The prev = dist[:] copy is the whole trick. Without it, you'd use updated distances from the current round, effectively allowing more edges than K+1.

Bellman-Ford vs Dijkstra vs Floyd-Warshall

Algorithm	Time	Space	Handles Negative	Negative Cycle	Use Case
Dijkstra	O((V+E) log V)	O(V)	No	No	Single source, non-negative
Bellman-Ford	O(VE)	O(V)	Yes	Detects	Single source, negative OK
Floyd-Warshall	O(V^3)	O(V^2)	Yes	Detects	All pairs shortest paths

Choose based on what the problem requires. If you're asked about negative weights or negative cycles, it's Bellman-Ford. If you need all-pairs, Floyd-Warshall. Everything else, Dijkstra.

SPFA — The Practical Optimization

Shortest Path Faster Algorithm is a queue-based optimization of Bellman-Ford. Instead of relaxing all edges every iteration, only relax edges from vertices whose distances changed. Use a queue to track which vertices to process.

from collections import deque

def spfa(n, adj, source):
    """adj: adjacency list, adj[u] = [(v, w), ...]"""
    dist = [float('inf')] * n
    dist[source] = 0
    in_queue = [False] * n
    queue = deque([source])
    in_queue[source] = True

while queue:
        u = queue.popleft()
        in_queue[u] = False

for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True

return dist

SPFA is typically much faster than standard Bellman-Ford in practice. Worst case is still O(VE), but average case is close to O(E) on random graphs. Some competitive programmers swear by it; others consider it unreliable for worst-case guarantees.

Reconstructing the Path

Track predecessors during relaxation:

def bellman_ford_path(n, edges, source, target):
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0

for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

# reconstruct
    if dist[target] == float('inf'):
        return None

path = []
    current = target
    while current != -1:
        path.append(current)
        current = prev[current]

return path[::-1]

Same approach as Dijkstra's path reconstruction. The predecessor array records which vertex led to each shortest path update.

Common Mistakes

Using Bellman-Ford when Dijkstra works. If all weights are non-negative, Bellman-Ford is just a slower Dijkstra. Don't waste time. Not copying distances in the K-edges variant. This is the number one bug in the cheapest flights problem. Without copying, you allow longer paths in a single iteration. Checking dist[u] != inf before relaxing. This guard is important — without it, you'd relax from unreachable vertices using inf + w, which can cause overflow or incorrect results. Confusing "no path" with "negative cycle." Bellman-Ford returns infinity for unreachable vertices and null (or an indicator) for negative cycles. They're different conditions. Iterating V times instead of V-1. The Vth iteration is the negative cycle check, not part of normal relaxation. If you do V relaxation rounds and then check, you've done V+1 total — one too many for cycle detection.

Work through these problems on CodeUp to build intuition for when Bellman-Ford is the right call versus Dijkstra.