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

Bellman-Ford detects a negative cycle reachable from the source when a reachable edge can still relax after V−1 rounds. Only vertices reachable from such a cycle lose a finite shortest distance; unrelated vertices do not. For currency arbitrage, transform a rate r to weight -log(r) so a profitable product becomes a negative sum.

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