Bellman-Ford: When Edges Can Be Negative

"Dijkstra trusts that getting farther can only cost more. Negative edges break that trust. Bellman-Ford is the patient, slower algorithm that makes no such assumption — and can even detect when 'cheapest' has no answer at all."

The Case Dijkstra Can't Handle

Some edges genuinely have negative weights: a currency exchange that nets a gain, a financial flow that's a credit, a game move that restores health. Dijkstra fails here because its core assumption — finalizing the closest node is safe — relies on every edge adding cost. A negative edge could let a node you'd already finalized be reached more cheaply later. Bellman-Ford drops that assumption entirely, at the price of being slower.

The Algorithm: Relax Everything, V−1 Times

Bellman-Ford is almost brutally simple: relax every edge in the graph, and repeat that V−1 times. 'Relax edge u→v' means: if reaching v through u is cheaper than v's current distance, update it. Why exactly V−1 rounds? Because a shortest path in a graph of V nodes uses at most V−1 edges, and each full round of relaxing all edges guarantees correct distances propagate one more edge outward from the source. After V−1 rounds, every shortest path (at most V−1 edges long) has been fully resolved. It's O(V·E) — slower than Dijkstra's O((V+E) log V) — but it tolerates negatives.

Bellman-Ford relaxes all edges V−1 times — enough rounds for correct distances to propagate along any shortest path (≤ V−1 edges). It's O(V·E), slower than Dijkstra, but it handles negative weights and detects negative cycles. Dijkstra is the default; Bellman-Ford is the fallback when negatives are possible.

The Superpower: Negative-Cycle Detection

Here's something Dijkstra can't even attempt. If a graph has a negative cycle — a loop whose total weight is negative — then 'shortest path' is meaningless: you could circle that loop forever, getting cheaper each time, distance diving to negative infinity. Bellman-Ford detects this elegantly: after the V−1 rounds, do one more round. If any edge can still be relaxed (still improves), a negative cycle exists. This is exactly how currency arbitrage is detected — model exchange rates as a graph, and a negative cycle is a sequence of trades that returns more money than you started with. The algorithm that finds 'no answer exists' is sometimes the most valuable one.

Pippa's Confession

Negative cycles bent my brain — how can a shortest path be negative infinity? Dad gave me the arbitrage picture: trade dollars→euros→yen→dollars and end with more than you started. Loop it forever and you're infinitely rich; there's no 'shortest' because cheaper always exists. Bellman-Ford's extra round isn't a quirk — it's the algorithm honestly reporting 'this question has no answer.' I learned that detecting impossibility is a feature, not a failure.

Code

Bellman-Ford with negative-cycle detection·python

def bellman_ford(nodes, edges, source):
    """Shortest distances allowing negative weights. Detects negative cycles.
    edges: list of (u, v, weight). O(V * E)."""
    dist = {n: float('inf') for n in nodes}
    dist[source] = 0

    # Relax ALL edges, V-1 times.
    for _ in range(len(nodes) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:      # relax: cheaper route to v via u
                dist[v] = dist[u] + w

    # One MORE round: if anything still improves, there's a negative cycle.
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected — no shortest path exists")
    return dist

nodes = ["A", "B", "C", "D"]
edges = [("A","B",4), ("A","C",5), ("B","C",-3), ("C","D",2)]  # B->C is negative
print(bellman_ford(nodes, edges, "A"))   # {'A':0,'B':4,'C':1,'D':3} (A->B->C=1)

# A negative cycle makes 'shortest' meaningless:
cyc_nodes = ["X", "Y", "Z"]
cyc_edges = [("X","Y",1), ("Y","Z",-3), ("Z","X",1)]   # cycle total = -1
try: bellman_ford(cyc_nodes, cyc_edges, "X")
except ValueError as e: print(e)   # negative cycle detected

Exercise

Explain in your own words why Bellman-Ford needs exactly V−1 relaxation rounds (hint: how many edges can a shortest path have?). Then describe how the Vth round detects a negative cycle, and give a real-world example where detecting that cycle is the actual goal rather than the distances.

Hint

A shortest path visits at most V nodes, so at most V−1 edges; each round propagates correct distances one edge farther, so V−1 rounds settle every shortest path. If a Vth round still improves something, a negative cycle exists — exactly how currency arbitrage (a trade loop that nets profit) is detected.

The Case Dijkstra Can't Handle

The Algorithm: Relax Everything, V−1 Times

The Superpower: Negative-Cycle Detection

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0