Bellman-Ford: Shortest Paths With Negative Edge Weights, Explained

Quick Answer

Bellman-Ford finds the shortest path from a source node to every other node, even when some edges have negative weights, which breaks Dijkstra's algorithm. It works by relaxing every edge in the graph, up to n-1 times, where n is the number of nodes, gradually tightening distance estimates until no further improvement is possible. One extra pass after that tells you whether a negative-weight cycle exists at all, in which case "shortest path" has no real answer.

The problem Dijkstra can't handle

Dijkstra's algorithm finds shortest paths by always expanding the closest unvisited node next, and locking in ("finalizing") its distance permanently once it's been processed. That locking-in step is exactly where the algorithm assumes every edge weight is non-negative: once a node is finalized at its current best-known distance, Dijkstra never revisits it, on the assumption that no future edge could possibly make an already-visited node even cheaper to reach, since adding any further non-negative edge weight can only increase a distance, never decrease it.

Negative edge weights break that assumption directly. If some edge can subtract from a path's total cost, then a node that looked "done" early on, because the cheapest path found so far was small, might actually have a much better path through a node that gets discovered later. Dijkstra has no mechanism to go back and fix that, because by design it never looks at a finalized node again.

This isn't a hypothetical corner case. Negative weights show up in real problems: currency arbitrage detection (think of exchange-rate ratios as edge weights, where a profitable cycle is a negative-weight cycle in disguise), certain network-routing cost models where some paths are actively incentivised with a rebate, and any graph where "weight" represents something other than a literal non-negative distance, like profit, time saved, or risk reduction.

What Bellman-Ford does differently

Bellman-Ford doesn't try to be clever about processing order at all. It just relaxes every single edge in the graph, repeatedly, for up to n-1 rounds (where n is the number of nodes). "Relaxing" an edge (u, v, w) means checking: is the best known distance to u, plus this edge's weight w, smaller than the best known distance to v so far? If so, update v's distance. Because it never assumes any node is "done" until all n-1 rounds complete, it has no equivalent blind spot, it simply keeps revisiting every edge until nothing changes.

How relaxing every edge, repeatedly, finds the correct answer

The core guarantee behind Bellman-Ford is a simple counting argument: in a graph with no negative cycles, the shortest path between any two nodes uses at most n-1 edges (since a shortest path never needs to revisit the same node twice, and there are only n nodes total). So if, on each full round, you relax every edge in the graph, in the worst case it takes n-1 rounds for the "correct" shortest-path information to propagate all the way from the source to the farthest node, one additional edge's worth of correctness per round.

Concretely: after round 1, every node that's reachable from the source via a single edge has its correct shortest distance. After round 2, every node reachable via at most two edges has its correct distance (because by then, the first-edge nodes already have correct values from round 1, so relaxing again propagates correctly into their neighbours). This continues outward, one "edge of distance" per round, until round n-1 guarantees correctness for every node, no matter how many edges its shortest path actually needs, up to the maximum possible.

In practice, most graphs converge far earlier than n-1 rounds, which is why a well-implemented version checks whether any edge was actually relaxed during a round, and exits early the moment a full round changes nothing. The implementation below does exactly that with its updated flag.

Why n-1 rounds, specifically, and not fewer

Picture a graph that's just a straight chain of n nodes, 0 -> 1 -> 2 -> ... -> (n-1), each edge pointing forward. The shortest path from node 0 to node n-1 necessarily uses all n-1 edges. If you relaxed the edges in exactly the wrong order, say from the far end backward, each single round would only manage to propagate the correct distance one more hop. So the worst case genuinely requires n-1 full rounds, this isn't a loose, pessimistic bound, it's tight.

Detecting negative-weight cycles

If a negative cycle exists and is reachable from the source, "shortest path" stops being a well-defined question, you could keep going around the cycle forever, making the total cost lower every single lap. There is no minimum.

Bellman-Ford detects this with one clean extra step: after the n-1 relaxation rounds finish, do one more pass over every edge. If any edge can still be relaxed (meaning dist[u] + w < dist[v] still holds for some edge), that's proof a negative cycle exists, because in a cycle-free graph, n-1 rounds would already have found every node's true minimum, and a further improvement would be impossible.

This is a genuinely elegant property: the same algorithm that computes shortest paths also, almost for free, tells you when the question you asked doesn't have an answer. Dijkstra has no equivalent safety check, and as the counterexample later in this article shows, running Dijkstra on a graph with a reachable negative cycle doesn't just give a wrong answer, it can fail to terminate at all, because its relaxation loop keeps finding "improvements" around the cycle indefinitely.

Walking through the actual detection step on the negative-cycle graph used later in this article makes it concrete: after the n-1 regular rounds finish, the extra verification pass checks every edge once more. For the cycle 1 -> 2 -> 3 -> 1 (weights -1, -1, -1, summing to -3), the edge from 3 back to 1 will always find that going to 3 and then back to 1 still beats the current best distance to 1, no matter how many rounds already ran, because going around the cycle one more time always shaves off another unit of distance. That single failing check, on an edge that should have stabilized if the graph were cycle-free, is the entire proof. No separate cycle-finding algorithm (like a depth-first-search-based cycle detector) is needed on top of the shortest-path computation you were already doing.

Python implementation, and a real run

Here's the complete implementation, including the early-exit optimisation and the negative-cycle check:

def bellman_ford(n, edges, source):
    dist = [math.inf] * n
    dist[source] = 0
    parent = [-1] * n
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                updated = True
        if not updated:
            break
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != math.inf and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break
    return dist, parent, has_negative_cycle

Run against a graph with a genuine negative edge, but confirmed to have no negative cycle:

edges = [
    (0, 1, 4), (0, 2, 7), (1, 2, -3),   # negative edge
    (2, 3, 5), (1, 3, 9), (3, 4, 2), (0, 4, 20),
]
dist, parent, neg_cycle = bellman_ford(5, edges, 0)

Graph 1 (has a negative edge, confirmed no negative cycle):
distances from 0: [0, 4, 1, 6, 8]
negative cycle detected by Bellman-Ford: False
Dijkstra on the SAME graph ran in 8 pop operations, bailed_out=False
Dijkstra distances:    [0, 4, 1, 6, 8]
Bellman-Ford distances: [0, 4, 1, 6, 8]
Do they match? True

Bellman-Ford and (in this specific graph, which happens to have no back-edges at all) even a lazily-reinserting Dijkstra variant agree here. That's expected, Dijkstra's failure mode needs a specific structural condition that this particular graph doesn't trigger. The next section builds a graph that does trigger it, on purpose, to show exactly where and why Dijkstra breaks.

Run against a graph with a genuine negative cycle (1 -> 2 -> 3 -> 1, total weight -3):

Graph 2 (genuine negative cycle 1 -> 2 -> 3 -> 1, total weight -3):
negative cycle detected: True

Bellman-Ford correctly flags this without needing any special-cased cycle-detection logic beyond the one extra pass. Note that this article deliberately does not run Dijkstra on this second graph: with a true negative cycle reachable from the source, Dijkstra's relaxation loop has no natural stopping point and will keep finding improvements around the cycle forever. (This was discovered the hard way while preparing this article, an earlier draft graph had an accidental negative cycle, and a Dijkstra comparison against it hung indefinitely until it was killed and the graph was fixed, which is as real a demonstration of the failure mode as any crafted example could be.)

The exact moment Dijkstra breaks, proven on a 4-node graph

To show precisely where Dijkstra goes wrong, not just assert that it does, here's a small, deliberately constructed graph with no cycle at all, just four nodes and four edges, where a textbook Dijkstra implementation (one that marks a node as permanently visited the moment it's popped from the priority queue) gives a provably wrong answer:

def dijkstra_textbook(n, edges, source):
    # Textbook Dijkstra: once a node is popped, it is marked visited and
    # NEVER reconsidered again, even if a cheaper route turns up later.
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [math.inf] * n
    dist[source] = 0
    visited = [False] * n
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        for v, w in adj[u]:
            if not visited[v] and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# S=0, A=1, C=2, B=3
# S->A direct = 1 (small, so A gets finalized almost immediately)
# S->C = 2, then C->A = -10 (a much cheaper route into A,
# but discovered AFTER A is already finalized)
edges = [
    (0, 1, 1),    # S->A
    (0, 2, 2),    # S->C
    (2, 1, -10),  # C->A, negative edge back into an already-finalized node
    (1, 3, 100),  # A->B
]

The idea: node A has two routes in. The direct route (S to A, weight 1) is cheap enough that Dijkstra finalizes A almost immediately, before it has looked at the alternate route through C at all. Only later does it discover that going through C first (S to C, weight 2, then C to A, weight -10) actually reaches A for a total of -8, far cheaper than the 1 it already locked in. But A is already finalized by then, and a finalized node is never reconsidered, so that better route is simply lost. Running both algorithms on this exact graph:

Bellman-Ford (correct):    [0, -8, 2, 92]
Textbook Dijkstra (wrong): [0, 1, 2, 101]
Match? False

A's true shortest distance from S is -8 (via S->C->A: 2 + -10 = -8)
but Dijkstra finalized A at distance 1 (via direct S->A: 1) before
it ever saw the cheaper C->A edge, and a finalized node is never revisited.
That stale distance then propagates: B ends up wrong too, at 101
instead of 92.

This is not a contrived edge case dressed up to look dramatic, it's the literal mechanism by which negative edges break Dijkstra: an early, cheap-looking path gets locked in before a later, genuinely cheaper negative-weight path is discovered, and the finalization step has no way to undo that mistake. Bellman-Ford never finalizes anything until all n-1 rounds complete, so it has no equivalent blind spot, visible directly in the matching, correct output above.

Complexity, and what you're actually paying for correctness

Bellman-Ford runs in O(V*E) time, where V is the number of nodes and E is the number of edges, since it does up to V-1 rounds, each relaxing every one of the E edges. Space complexity is O(V) for the distance and parent arrays.

Dijkstra, by comparison, runs in O((V + E) log V) with a binary heap, which is meaningfully faster on sparse graphs with many nodes. That speed is exactly what you give up by choosing Bellman-Ford: you're trading a better asymptotic bound for the ability to handle negative edges and to detect negative cycles at all. If you know for certain your graph has no negative weights, Dijkstra is almost always the better choice. The moment negative weights are even possible, Bellman-Ford (or a variant like SPFA, which optimizes the average case using a queue of "active" nodes instead of blindly relaxing every edge every round) becomes the only correct option between the two.

To make the gap concrete: on a graph with 10,000 nodes and 50,000 edges, Dijkstra with a binary heap does roughly (V+E) log V operations, on the order of a few hundred thousand. Bellman-Ford, by contrast, does up to V*E operations in the worst case, 500 million here, a difference of roughly three orders of magnitude. That gap only grows as graphs get denser. This is exactly why production routing and pathfinding systems default to Dijkstra (or A* with a good heuristic) whenever they can guarantee non-negative weights, and only fall back to Bellman-Ford, or a queue-optimized variant like SPFA, when negative weights are a genuine possibility in the problem domain itself.

A useful rule of thumb for interviews and real design decisions alike: reach for Bellman-Ford specifically because of what it tolerates (negative edges) and what it can tell you (cycle existence), not because it's ever meant to be the fast option.

Where this shows up in real systems

Three concrete places this algorithm, or a close variant of it, actually earns its place in production systems rather than staying a textbook exercise:

• Distance-vector routing protocols. Early internet routing protocols like RIP (Routing Information Protocol) are essentially a distributed version of Bellman-Ford, where each router relaxes its known distances based on what its neighbours report, repeated until the whole network converges.
• Currency arbitrage detection. Model each currency as a node and each exchange rate as a directed edge weighted by the negative logarithm of the rate. A profitable arbitrage loop (buy currency A, convert through B and C, end up with more A than you started with) corresponds exactly to a negative-weight cycle in this graph, which Bellman-Ford's cycle check finds directly.
• Constraint-propagation and scheduling systems. Difference constraints of the form "event B must happen at least k units after event A" map naturally onto a shortest-path graph, and allowing negative k (B can happen before A, within a bound) is exactly the negative-edge case Bellman-Ford was built for.

The currency arbitrage case is worth spelling out mathematically since the negative-log trick isn't obvious on first read. If currency A converts to currency B at rate r (one unit of A buys r units of B), model that conversion as an edge weighted by the negative logarithm of r. Multiplying exchange rates along a conversion path corresponds to adding their logarithms, so a path where the product of rates exceeds 1 (a profitable round trip) corresponds to a path where the sum of negative-log-rates is negative, exactly a negative-weight cycle. This is a genuinely practical application: several real quantitative trading systems use almost precisely this Bellman-Ford-based cycle search to scan for arbitrage opportunities across currency pairs or exchange order books in close to real time.

In each case, the same property matters: once negative weights are possible (which a real exchange-rate or constraint model often requires), Dijkstra is the wrong tool even if it would run faster, because a fast wrong answer isn't useful.

Frequently Asked Questions