Negative edges and Bellman–Ford

Lesson · 12 min read · Graphs · Shortest paths from one source

One negative edge breaks Dijkstra. Relaxing every edge n − 1 times does not, and one more round exposes negative cycles.

Where Dijkstra goes wrong

Negative weights are not exotic: a rebate on a route, a profitable conversion in a chain of currency trades (logarithms of exchange rates turn products into sums, and gains into negative weights).

Dijkstra settles a at 2, the smallest tentative distance. The route s → b → a costs 5 − 4 = 1.

When a is settled, the argument "any other route passes an unsettled node with a larger distance, then edges that cannot reduce it" fails on its last step: the edge b → a reduces it.

Relax everything, repeatedly

Bellman–Ford gives up on settling nodes in the right order and instead relaxes every edge, in any order, in rounds. After round k, every node whose shortest path uses at most k edges has its correct distance: the path's last edge was relaxed in round k, after its second-to-last node was already correct.

A shortest path never repeats a node (unless there is a negative cycle), so it has at most n − 1 edges, and n − 1 rounds suffice. If a round changes nothing, later rounds will not either, and the algorithm can stop early.

Bellman–Ford

bellmanFord(n, edges, s)

Set dist[s] = 0 and all others to ∞.
Repeat n − 1 times: for every edge (u, v, w), if dist[u] + w < dist[v], set dist[v] = dist[u] + w.
One more pass: if any edge can still be relaxed, report a negative cycle.
Return dist.

Step by step

The edges below are listed in an unhelpful order (the last edge of each path first), so each round pushes correct distances only one edge further. In the best order a single round would do.

Bellman–Ford from node 0, one frame per round. Edges are relaxed in the order 3→4, 2→3, 1→2, 0→1, 0→2, 0→3, 1→3.

Step 1 / 6

Start: the source 0 is at 0, everything else at ∞. Edges are relaxed in the order they are listed.
Step 2 / 6

Round 1: 1: ∞ → 4 via 0; 2: ∞ → 5 via 0; 3: ∞ → 8 via 0.
Step 3 / 6

Round 2: 4: ∞ → 10 via 3; 3: 8 → 6 via 2; 2: 5 → 2 via 1.
Step 4 / 6

Round 3: 4: 10 → 8 via 3; 3: 6 → 3 via 2.
Step 5 / 6

Round 4: 4: 8 → 5 via 3.
Step 6 / 6

A check round: no edge can be improved, so there is no negative cycle and the distances are final.

current best predecessorstill improvable after n − 1 rounds

Negative cycles

If a cycle's weights add up to less than zero, going round it once more always lowers the total, so nodes on or after the cycle have no shortest distance at all. Bellman–Ford detects this: after n − 1 rounds, an edge that can still be relaxed proves a negative cycle reachable from the source.

a → b → c → a sums to 2 − 6 + 3 = −1. Each lap lowers every distance on the cycle by 1.

This is the standard test for an arbitrage loop: with weights −log(rate), a sequence of conversions that returns more than it started with is exactly a negative cycle.

Implementation

Distances from a source, 10⁹ for unreachable nodes, and an empty list if a negative cycle is reachable:

def bellman_ford(n, edges, src):
    INF = 10**9
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:   # never relax from an unreached node
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                       # nothing can change any more
    for u, v, w in edges:               # one more round: any improvement means a negative cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return []
    return dist

#include <vector>

std::vector<long long> solve(int n, const std::vector<std::vector<int>>& edges, int src) {
    const long long INF = 1000000000;
    std::vector<long long> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round < n - 1; ++round) {
        bool changed = false;
        for (const auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
        }
        if (!changed) break;                       // nothing can change any more
    }
    for (const auto& e : edges)                    // a further improvement: negative cycle
        if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return {};
    return dist;
}

class Solution {
    public int[] bellmanFord(int n, int[][] edges, int src) {
        final int INF = 1_000_000_000;
        int[] dist = new int[n];
        java.util.Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 0; round < n - 1; round++) {
            boolean changed = false;
            for (int[] e : edges) {
                if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; changed = true; }
            }
            if (!changed) break;                   // nothing can change any more
        }
        for (int[] e : edges)                      // a further improvement: negative cycle
            if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) return new int[0];
        return dist;
    }
}

function bellmanFord(n, edges, src) {
  const INF = 1e9;
  const dist = new Array(n).fill(INF);
  dist[src] = 0;
  for (let round = 0; round < n - 1; round++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] !== INF && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
    }
    if (!changed) break;               // nothing can change any more
  }
  for (const [u, v, w] of edges) {     // a further improvement means a negative cycle
    if (dist[u] !== INF && dist[u] + w < dist[v]) return [];
  }
  return dist;
}

fn solve(n: i64, edges: &[[i64; 3]], src: i64) -> Vec<i64> {
    const INF: i64 = 1_000_000_000;
    let n = n as usize;
    let mut dist = vec![INF; n];
    dist[src as usize] = 0;
    for _ in 0..n.saturating_sub(1) {
        let mut changed = false;
        for e in edges {
            let (u, v, w) = (e[0] as usize, e[1] as usize, e[2]);
            if dist[u] != INF && dist[u] + w < dist[v] {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if !changed {
            break;                                 // nothing can change any more
        }
    }
    let negative_cycle = edges.iter().any(|e| {
        let (u, v) = (e[0] as usize, e[1] as usize);
        dist[u] != INF && dist[u] + e[2] < dist[v]
    });
    if negative_cycle { Vec::new() } else { dist }
}

import Data.List (foldl')
import qualified Data.Map.Strict as M

solve :: Int -> [[Int]] -> Int -> [Int]
solve n edges src
  | any improves edges = []                       -- a further improvement: negative cycle
  | otherwise = [M.findWithDefault inf v final | v <- [0 .. n - 1]]
  where
    inf = 1000000000
    start = M.singleton src 0
    -- one round relaxes every edge; nodes absent from the map are unreached
    relax d [u, v, w] = case M.lookup u d of
      Just du | du + w < M.findWithDefault inf v d -> M.insert v (du + w) d
      _ -> d
    rounds k d
      | k == 0 = d
      | d' == d = d                                 -- nothing changed: stop early
      | otherwise = rounds (k - 1) d'
      where d' = foldl' relax d edges
    final = rounds (n - 1) start
    improves [u, v, w] = case M.lookup u final of
      Just du -> du + w < M.findWithDefault inf v final
      Nothing -> False

The same code is the reference solution to Shortest distances with negative edges, where it is compiled and run against the tests in all six languages.

TimeO(n · m)

SpaceO(n)

Slower than Dijkstra by a factor of roughly n / log n, which is the price of allowing negative weights. On graphs with no negative edges, use Dijkstra.

Limiting the rounds to k + 1 answers "cheapest route with at most k stops", as long as each round reads the distances from the previous round rather than the ones it is updating. The problem at the end of this module needs exactly that.