Shortest Path Algorithms: Bellman-Ford & Negative Weights

Graph Theory

Chapter 7 · Shortest Path Algorithms: Bellman-Ford & Negative Weights

Chapter 6 ended with a genuine failure: Dijkstra reported D=101 for a graph where the true shortest distance was 94, because a negative edge corrected a vertex's distance after that vertex had already been greedily finalized. This chapter fixes exactly that failure — with an algorithm that never finalizes anything early enough to get caught out.

The Idea: Stop Trusting Any Distance Until Enough Rounds Have Passed

Where Dijkstra finalizes one vertex at a time and never looks back, Bellman-Ford takes the opposite approach: it relaxes every single edge in the graph, repeatedly, for a fixed number of rounds — giving corrections like the one that broke Dijkstra time to propagate all the way through, no matter how many extra hops away they start.

The mechanism

Initialize distances exactly as before (source = 0, everything else = infinity). Repeat V − 1 times (V = number of vertices): for every edge (u, v, w) in the graph, if dist[u] + w < dist[v], update dist[v]. No priority queue, no "finalizing" — just brute-force relaxation, over and over.

Why Exactly V − 1 Rounds?

A shortest path that doesn't repeat any vertex (a "simple" path) can use at most V − 1 edges — there are only V vertices to visit at all. Each full round of relaxing every edge guarantees that any shortest path using up to that many edges gets found: round 1 finds every shortest path of 1 edge, round 2 extends those into every shortest path of up to 2 edges, and so on. After V − 1 rounds, every possible simple shortest path — however many edges it needs — has been fully accounted for.

Fixing Chapter 6's Own Counterexample

Same graph that broke Dijkstra: A→B(1), A→C(4), C→B(−10), B→D(100). 4 vertices, so 3 rounds.

Traced and verified directly

Relaxing every edge, in order, during round 1: A→B gives B=1. A→C gives C=4. C→B: 4−10=−6, beats B's current 1 — B corrected to −6. B→D: −6+100=94. Round 2 finds nothing left to improve — the algorithm has already converged. Final distances: {A:0, B:−6, C:4, D:94}. D is now correctly 94, not Dijkstra's wrong 101 — because B's correction happened before B→D was ever relied on again, simply by relaxing every edge in the same pass rather than committing to B's value early.

The edge processing order still matters within a round

Processing the edges in a less convenient order (e.g. B→D listed before C→B) means D doesn't get its correct value until round 2 instead of round 1 — verified directly. Either way, by the time all V−1 rounds are done, the answer is guaranteed correct regardless of what order the edges happen to be listed in — only the number of rounds needed to get there changes, not the final result.

The Extra Round: Detecting Negative Cycles

Everything above assumes a shortest simple path exists at all. If the graph contains a negative cycle — a cycle whose total edge weight sums to less than zero — there is no shortest path at all, since going around the cycle again and again keeps reducing the total cost forever. Bellman-Ford detects this directly: run one extra (a V-th) round of relaxation — if any edge can still be relaxed after the normal V−1 rounds finished, a negative cycle reachable from the source must exist.

Graph: A→B(1), B→C(−1), C→A(−1) — a triangle whose total weight is 1 + (−1) + (−1) = −1.

Verified directly

After the normal 2 rounds (V=3), distances are still shrinking. Running the extra check round finds edge A→B still relaxable (dist[A]+1 < dist[B]) — the negative-cycle signature. Correctly flagged: negative cycle detected.

Real Relevance: Currency Arbitrage Detection

This is Bellman-Ford's single most-cited real application: model each currency as a vertex, each exchange rate as an edge weighted −log(rate). A cycle of exchanges is profitable exactly when the product of its rates exceeds 1 — which, because −log turns multiplication into addition, is exactly when the sum of −log(rate) around that cycle is negative. A negative cycle in this graph is a real, mechanically-detectable arbitrage opportunity.

Verified directly

USD→EUR at 0.9, EUR→GBP at 0.8, GBP→USD at 1.5. Product: 0.9 × 0.8 × 1.5 = 1.08 — trading through the full cycle turns $1 into $1.08, an 8% profit. Sum of −log(rate) around the same cycle: −0.077 — negative, exactly as the theory predicts, and exactly what Bellman-Ford's negative-cycle check would flag.

When to Reach for Bellman-Ford Instead of Dijkstra

	Dijkstra	Bellman-Ford
Negative weights	Unsupported — silently wrong (Chapter 6)	Fully supported
Negative cycles	No detection at all	Detects them directly
Time complexity	O((V+E) log V) with a priority queue	O(V × E) — every edge, every round
Use when	All weights are known to be non-negative (the common case — distances, times, costs)	Negative weights are possible, or a negative cycle itself needs detecting

Bellman-Ford is strictly more capable, but genuinely slower on large graphs — the right default is still Dijkstra whenever negative weights are known to be impossible, reaching for Bellman-Ford specifically when they aren't.

Bellman-Ford in Code

def bellman_ford(vertices, edges, source):
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0

    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # extra round: still-relaxable edge = negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return dist, True   # negative cycle found

    return dist, False

vertices = ['A','B','C','D']
edges = [('A','B',1), ('A','C',4), ('C','B',-10), ('B','D',100)]
print(bellman_ford(vertices, edges, 'A'))  # ({'A':0,'B':-6,'C':4,'D':94}, False)

Hands-On Exercises

Exercise 1

Using Bellman-Ford, find the shortest distances from source S for: S→T(6), S→U(7), T→U(−3), U→V(2). Show each round, and how many rounds it actually takes to stop changing.

📄 View solution

Exercise 2

Run Bellman-Ford's negative-cycle check on the graph P→Q(2), Q→R(2), R→P(−5). Determine whether a negative cycle exists, and if so, state its total weight.

📄 View solution

Exercise 3

A trader finds three exchange rates: USD→JPY at 110, JPY→GBP at 0.0068, GBP→USD at 1.3. Using this chapter's own arbitrage-detection method, determine whether trading through this full cycle is profitable, and by how much.

📄 View solution

Chapter 7 Quick Reference

Bellman-Ford: relax every edge in the graph, V−1 times — no priority queue, no early finalizing
V−1 rounds is exactly enough because a simple shortest path can use at most V−1 edges
Negative cycle detection: if any edge is still relaxable after V−1 rounds, a negative cycle exists
Correctly solves Chapter 6's own counterexample — D=94, not Dijkstra's wrong 101
Currency arbitrage: weight edges by −log(rate); a negative cycle is a real, detectable profit opportunity
O(V×E), slower than Dijkstra's O((V+E) log V) — use Dijkstra by default, Bellman-Ford only when negative weights are possible
Next chapter: Minimum Spanning Trees — Kruskal's & Prim's algorithms