Bellman-FordShortest paths with negative weights

01Why it exists

Reach for it when you see:Negative edge weights, negative cycles, arbitrage, at most k edges, distance-vector routing, difference constraints x_j − x_i ≤ c, shortest paths where Dijkstra does not apply, modest V and E.

02The core idea

Bellman-Ford picks no order and finalises no node. It does exactly one thing: relax every edge once, which is called a round, then repeat. Every dist starts at ∞ except the source, and each round checks dist[u] + w < dist[v] for every edge u → v, updating when it holds. The guarantee it buys you is this: after round k, dist[v] is no larger than the shortest distance to v using at most k edges. Induction makes it clear — for a shortest path of at most k+1 edges, the node u reached by its first k edges already has a dist no larger than that prefix by the end of round k, so when round k+1 sweeps over the final edge u → v it pushes dist[v] down.

With no negative cycle, a shortest path is always a simple path (going around a loop can only make it longer or leave it unchanged), so it uses at most V − 1 edges and after V − 1 rounds dist is the correct answer. Nothing in that argument assumed non-negative weights, which is why negative edges cause no trouble here. Dijkstra cannot do this because it finalises a node's distance the moment it is popped, on the assumption that no shorter route can appear later; with negative edges, a route found later may well be shorter. On the graph in the demo, finalise-on-pop Dijkstra would fix A at 6 and D at 2, when the true shortest distances are 2 and −2.

Negative-cycle detection: if the start can reach a cycle whose weights sum to a negative number, you can go around it forever to get shorter, and shortest paths have no definition. In that case some edge must still be relaxable after round V − 1 — otherwise adding the inequalities around the cycle would give a total weight ≥ 0, a contradiction — so sweep a Vth round, and any update means there is a negative cycle. To recover the cycle itself, note a node updated on round V and walk back along parent V steps, which is guaranteed to land on the cycle, then go around once to collect its nodes. Complexity is V rounds times E edges per round: O(VE) time and O(V) space. A round with no updates lets you stop early, and in practice that often happens well short of V − 1 rounds. SPFA uses a queue to re-check only the nodes whose distance just dropped, which is much faster on average, but its worst case is still O(VE) and inputs designed to slow it down do exist.

The usual traps: relaxing out of a node with dist = ∞, where ∞ plus a negative weight is still a huge number but may look "shorter", so always check dist[u] != ∞ first, and leave headroom in the C++ INF so nothing overflows. In an undirected graph, a single negative edge is itself a negative cycle (u → v → u). To detect a negative cycle anywhere, set every dist to 0, which is the same as adding a virtual source joined to every node. And when the limit is "at most k edges" (LeetCode 787), each round must use only the previous round's distances, or one round may chain several edges together. Choosing between the algorithms: use Dijkstra for non-negative weights; on a DAG, topologically sort and then relax, which is O(V + E) and handles negative weights too; for all-pairs distances with a small V, use Floyd-Warshall.

03The algorithm

1. 1Set every dist to ∞ and dist[src] = 0. Storing the graph as a plain list of edges (u, v, w) is enough.
2. 2Repeat V − 1 rounds: for each edge, if dist[u] != ∞ and dist[u] + w < dist[v], update dist[v], also recording parent[v] = u when you need the path itself.
3. 3If a round makes no update at all, the distances have converged and you can stop early.
4. 4Sweep all the edges one more time: if anything can still be relaxed, there is a negative cycle reachable from the start, and shortest paths are undefined.
5. 5To recover the cycle: note a node updated in that sweep, walk back along parent V steps, then go around once collecting nodes. When at most k edges are allowed, relax each round against a copy of the previous round's dist.

04Interactive demo

Five nodes and ten directed edges, with negative weights written in yellow. "Example 1: negative edges, no negative cycle": round 1 alone makes six updates, round 2 has only A → D left, which pushes D from 2 down to −2, and round 3 changes nothing, so it stops early with A = 2 and D = −2. "Example 2: a negative cycle" changes C → A to −5, so going around A → D → C → A now sums to −2: every round still finds updates, even the source S is dragged below zero, and the check on round 5 after the four full rounds can still relax an edge. The negative cycle recovered along parent, C → A → D → C, is highlighted in yellow. As for the nodes, blue marks the one updated on this step and yellow marks nodes that already have a distance which may still change; a blue edge is one that relaxed successfully this round.

05Code

Python has the standard Bellman-Ford (with early exit and negative-cycle detection), a routine that recovers the cycle itself, and the "at most k edges" variation, all on the same graph as the interactive demo. C++ has Bellman-Ford and SPFA, each detecting negative cycles its own way: Bellman-Ford asks whether round V can still relax an edge, SPFA asks whether some shortest path has used V edges.

from math import inf


def bellman_ford(n, edges, src):
    """edges holds directed edges (u, v, w). Returns (dist, whether a negative cycle is reachable from src). O(VE)"""
    dist = [inf] * n
    dist[src] = 0
    for _ in range(n - 1):                    # with no negative cycle, a shortest path uses at most n − 1 edges
        changed = False
        for u, v, w in edges:
            if dist[u] != inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                       # a whole round with no update means it has converged
            break
    has_neg_cycle = any(dist[u] != inf and dist[u] + w < dist[v] for u, v, w in edges)
    return dist, has_neg_cycle


def find_negative_cycle(n, edges):
    """Returns the nodes of some negative cycle in edge order, or None if there is none"""
    dist = [0] * n                            # all zeros: same as a virtual source joined to every node
    parent = [-1] * n
    for _ in range(n):
        x = -1
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v], parent[v], x = dist[u] + w, u, v
    if x == -1:
        return None                           # round n updated nothing: no negative cycle
    for _ in range(n):
        x = parent[x]                         # n steps back is guaranteed to land on the cycle
    cycle, y = [x], parent[x]
    while y != x:
        cycle.append(y)
        y = parent[y]
    return cycle[::-1]


def shortest_with_k_edges(n, edges, src, k):
    """At most k edges may be used (for example, at most k − 1 layovers)"""
    dist = [inf] * n
    dist[src] = 0
    for _ in range(k):
        prev = dist[:]                        # only last round's values, so one round cannot chain several edges
        for u, v, w in edges:
            if prev[u] != inf and prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return dist


if __name__ == "__main__":
    S, A, B, C, D = range(5)                  # the same graph as the interactive demo
    edges = [(S, A, 6), (S, B, 7), (A, C, 5), (A, B, 8), (A, D, -4),
             (B, C, -3), (B, D, 9), (C, A, -2), (D, C, 7), (D, S, 2)]
    print(bellman_ford(5, edges, S))          # ([0, 2, 7, 4, -2], False)
    print(shortest_with_k_edges(5, edges, S, 2))   # [0, 6, 7, 4, 2] (only 2 edges allowed)

    neg = [(u, v, -5 if (u, v) == (C, A) else w) for u, v, w in edges]
    print(bellman_ford(5, neg, S)[1])         # True
    print(find_negative_cycle(5, neg))        # [4, 0, 2, 3, 1]: D→S→B→C→A→D sums to −3
    # The demo finds C→A→D→C (−2) instead: one graph can hold several negative cycles, and which one you land on depends on the scan order

06Practice

• LeetCode 743Network Delay Time (non-negative weights — write it with Bellman-Ford as well and compare against Dijkstra)Medium
• LeetCode 787Cheapest Flights Within K Stops (at most k+1 edges, each round using only the previous round's distances)Medium
• CSES 1197Cycle Finding (find and print a negative cycle)Medium
• LeetCode 1928Minimum Cost to Reach Destination in Time (relax in layers by time)Hard
• CSES 1673High Score (longest path: negate the weights and only count negative cycles that can reach the target)Hard