Graphs5 min read

Bellman-Ford Algorithm

Shortest paths with negative weights — and negative cycle detection

time: \(O(VE)\)space: \(O(V)\)

Dijkstra is fast but has one hard rule: no negative edge weights. Some real problems break that rule — currency exchange arbitrage, network cost models, or graphs where certain edges represent savings. That's where Bellman-Ford comes in.

Bellman-Ford finds the shortest path from one source node to all others, even when some edges have negative costs. It also detects a dangerous situation: a negative cycle — a loop whose total weight is negative. Going around it forever keeps lowering your cost, making the shortest path undefined.

The algorithm

Key insight: the shortest simple path in a graph with V nodes uses at most V-1 edges (any more and you revisit a node, creating a cycle). So: relax every edge, exactly V-1 times. After k passes, all shortest paths using at most k edges are finalized.

pseudocode

function bellmanFord(nodes, edges, start):
  dist = { all: Infinity }
  dist[start] = 0

  for i from 1 to V-1:
    for [from, to, weight] of edges:
      if dist[from] + weight < dist[to]:
        dist[to] = dist[from] + weight

  // Detect negative cycles
  for [from, to, weight] of edges:
    if dist[from] + weight < dist[to]:
      return 'Negative cycle detected'

  return dist

◈ Watch Bellman-Ford

← → arrow keys to step · click elements to interact

Bellman-Ford Algorithm

def bellman_ford(n, edges, src):
    """n = nodes, edges = [(u, v, weight)], src = source."""
    dist = [float('inf')] * n
    dist[src] = 0

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

    # Check for negative cycles
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None  # negative cycle detected

    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,2),(1,3,6)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 3]

Output

[0, 4, 1, 3]

Negative cycle detection

After V-1 passes all true shortest paths are finalized. If a V-th pass can still reduce a distance, some path is getting shorter because it loops through a negative cycle. Bellman-Ford catches this and reports it.

Bellman-Ford vs Dijkstra

Dijkstra: \(O((V+E)\) log V), requires non-negative weights, fast in practice
Bellman-Ford: \(O(VE)\), handles negative weights, detects negative cycles

Use Dijkstra when all weights are non-negative. Use Bellman-Ford when you have negative weights or need to detect negative cycles.

When does Bellman-Ford appear in practice?

Currency arbitrage detection (negative cycle = free money loop)
Network routing protocols (RIP uses Bellman-Ford)
Problems where edge weights represent relative gains/losses

Note: Bellman-Ford's V-1 passes are mathematically exact: the shortest path using exactly k edges is finalized after exactly k passes. There is no wasted work.

Complexity

TimeV-1 passes over all E edges

Slow\(O(VE)\)

SpaceDistance table for all nodes

Linear\(O(V)\)

Negative weight supportDijkstra cannot handle this

Yes—

Negative cycle detectionRun one extra pass after V-1

Yes—

Negative Cycle Detection

def has_negative_cycle(n, edges):
    dist = [0] * n  # start all at 0 to detect any 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  # cycle found
    return False

# Graph with negative cycle: 0->1->2->0 with weights 1, -3, 1 = total -1
print(has_negative_cycle(3, [(0,1,1),(1,2,-3),(2,0,1)]))  # True
print(has_negative_cycle(3, [(0,1,4),(1,2,2),(0,2,5)]))   # False

Output

True
False

Challenge

Quick check

Why does Bellman-Ford relax all edges exactly V-1 times?

Dijkstra's Algorithm

GPS for graphs — find the cheapest route from one node to all others

→

Floyd-Warshall Algorithm

All-pairs shortest paths in one elegant triple loop

→