Shortest Path — Bellman-Ford Algorithm

You've mastered Dijkstra's algorithm. You understand how it greedily selects the shortest-distance vertex, relaxes outgoing edges, and efficiently finds shortest paths using a priority queue. It's elegant, fast, and widely applicable. But there's a catch—one that can completely invalidate Dijkstra's results and lead to catastrophically wrong answers.

Dijkstra's algorithm fundamentally cannot handle graphs with negative edge weights.

This isn't a minor limitation or an edge case. In many real-world problems—financial arbitrage detection, network routing with incentives, game theory optimization, and scheduling with penalties—negative edges are not just possible but central to the problem domain. We need an algorithm that embraces negative weights rather than being broken by them.

Before diving into algorithms, let's establish a precise understanding of what negative edge weights mean and why they arise in practice.

What is an edge weight?

In a weighted graph, each edge (u, v) carries a numerical value called its weight, denoted w(u, v). This weight represents some cost, distance, or value associated with traversing from vertex u to vertex v. When we compute shortest paths, we're finding the path where the sum of edge weights is minimized.

Positive weights are intuitive: they represent costs we want to minimize. Distance in miles, time in seconds, monetary cost—all naturally positive quantities where more is worse.

Negative weights represent the opposite: traversing an edge reduces the total path cost. The edge provides a benefit, rebate, or reward rather than imposing a penalty.

Concrete example:

Consider a simple graph with three vertices A, B, and C:

• Edge A → B with weight 5
• Edge B → C with weight -3
• Edge A → C with weight 4

What's the shortest path from A to C?

Option 1: Direct A → C = 4 Option 2: A → B → C = 5 + (-3) = 2

The path through B is shorter! The negative edge from B to C provides enough 'discount' to offset the initial cost of reaching B. This is the essence of why negative weights matter—they can make longer paths (in hop count) shorter (in total weight).

Negative edge weights aren't academic curiosities—they model crucial real-world phenomena. Understanding these applications helps you recognize when Bellman-Ford is the right tool.

Deep Dive: Currency Arbitrage

One of the most famous applications involves detecting arbitrage opportunities in currency markets. Suppose you have exchange rates:

• 1 USD = 0.85 EUR
• 1 EUR = 130 JPY
• 1 JPY = 0.0095 USD

Starting with 1 USD, you could convert:

• USD → EUR: 0.85
• EUR → JPY: 0.85 × 130 = 110.5
• JPY → USD: 110.5 × 0.0095 ≈ 1.05 USD

You've turned 1 USD into 1.05 USD—a 5% profit! This is arbitrage, and it can be modeled as a shortest path problem.

The transformation trick:

To convert this to a shortest path problem, we take the negative logarithm of each exchange rate:

• -log(0.85) ≈ 0.162 (positive: unfavorable rate)
• -log(130) ≈ -2.114 (negative: favorable rate)
• -log(0.0095) ≈ 2.022 (positive)

Now, finding a path where the sum is negative corresponds to finding an arbitrage opportunity! If the total around a cycle is negative, you can profit by repeating that cycle. This is precisely a negative-weight cycle—and detecting such cycles is one of Bellman-Ford's superpowers.

Dijkstra's algorithm isn't just 'suboptimal' with negative weights—it can produce completely wrong results. Understanding why it fails illuminates both Dijkstra's fundamental assumptions and why Bellman-Ford's approach is necessary.

Dijkstra's Core Assumption: Greedy Finality

Recall how Dijkstra works:

1. Extract the vertex u with minimum tentative distance from the priority queue
2. Mark u as 'finalized'—its shortest distance is now known
3. Relax all outgoing edges from u
4. Never reconsider u again

The critical insight: once a vertex is extracted and finalized, Dijkstra assumes no shorter path to that vertex can ever be found. This is the greedy choice that makes Dijkstra efficient.

Why this assumption requires non-negative weights:

With non-negative weights only, if u is the unvisited vertex with minimum distance, no unvisited vertex can provide a shorter path to u. Any path going through another unvisited vertex v must first reach v (distance ≥ distance to u, by how we chose u) and then traverse at least one more edge (adding ≥ 0 to the cost). Therefore, such a path cannot be shorter.

Why negative weights break this:

With negative weights, a vertex v farther from the source might connect back to u via a negative edge, making the path s → v → u shorter than s → u directly. But by the time we discover this, we've already finalized u with the wrong distance!

Concrete Counterexample:

Consider this graph with source S:

    S ----3----> A
    |           |
    5          -2
    ↓           ↓
    B ----1----> C

• S → A: weight 3
• S → B: weight 5
• A → C: weight -2
• B → C: weight 1

Dijkstra's execution:

1. Initialize: dist[S]=0, dist[A]=∞, dist[B]=∞, dist[C]=∞
2. Process S: dist[A]=3, dist[B]=5
3. Extract A (min distance 3): dist[C] = 3 + (-2) = 1. Mark A finalized.
4. Extract C (min distance 1): Mark C finalized.
5. Extract B (distance 5): dist[C] would become 5 + 1 = 6, but C is already finalized with dist=1, so no update.
6. Done.

Dijkstra reports: dist[C] = 1

But wait! What about the path S → B → C?

S → B → C = 5 + 1 = 6. That's worse than 1, so Dijkstra seems correct... except I constructed a case where Dijkstra works by accident.

Let's try a different example:

    S ----2----> A ----3----> C
    |                        ↑
    4                       -5
    ↓                        |
    B ------------------------

• S → A: weight 2
• S → B: weight 4
• A → C: weight 3
• B → C: weight -5

Dijkstra's execution:

1. dist[S]=0, others ∞
2. Process S: dist[A]=2, dist[B]=4
3. Extract A (distance 2): dist[C] = 2 + 3 = 5. Mark A finalized.
4. Extract B (distance 4): dist[C] = min(5, 4 + (-5)) = min(5, -1) = -1. Update dist[C]=-1.
5. Extract C (distance -1): Mark C finalized.

Actually, in this case, Dijkstra updates C before finalizing it. But in many implementations, if C was already in the queue with distance 5= and we update it to -1, the old entry might still be processed first (depending on implementation).

The fundamental issue: Dijkstra might finalize vertices in the wrong order because it doesn't account for future negative edges improving distances.

The Fundamental Problem, Precisely Stated:

Dijkstra's correctness proof relies on the invariant that when a vertex is extracted from the priority queue, its distance is optimal and final. This invariant requires:

For any path P from source s to vertex v, if we extend P by one edge to reach w, the distance to w via this extended path is greater than or equal to the distance to v.

Mathematically: dist[v] + weight(v, w) ≥ dist[v]

This is only true if weight(v, w) ≥ 0 for all edges. The moment we allow weight(v, w) < 0, the invariant breaks, and Dijkstra's greedy finalization becomes unsafe.

We need an algorithm that doesn't rely on greedy finalization—one that's willing to reconsider and update distances even after a vertex seems 'done.' That algorithm is Bellman-Ford.

Where Dijkstra is a greedy algorithm—making locally optimal choices and never looking back—Bellman-Ford takes a fundamentally different approach. It's patient, methodical, and ultimately correct even when Dijkstra fails.

The Core Idea:

Bellman-Ford repeatedly relaxes all edges, not just those from the minimum-distance vertex. It does this V-1 times (where V is the number of vertices). After V-1 iterations, if the graph has no negative cycles reachable from the source, all shortest path distances are guaranteed to be correct.

Why V-1 iterations suffice:

A shortest path (without cycles) can have at most V-1 edges (visiting V vertices without repetition). Each iteration of Bellman-Ford correctly computes shortest paths using at most one more edge than the previous iteration:

• After iteration 1: Correct for all shortest paths with at most 1 edge
• After iteration 2: Correct for all shortest paths with at most 2 edges
• ...
• After iteration V-1: Correct for all shortest paths with at most V-1 edges

Since no simple shortest path has more than V-1 edges, we're guaranteed correct results after V-1 iterations.

The Relaxation Operation (Review):

Both algorithms rely on the same fundamental operation—relaxation. For an edge (u, v) with weight w:

if dist[v] > dist[u] + w:
    dist[v] = dist[u] + w
    predecessor[v] = u

Relaxation checks: 'Is the known path to v longer than going through u?' If so, update the path to v.

The difference is when and how often relaxation is applied:

• Dijkstra relaxes edges once per vertex, in carefully chosen order
• Bellman-Ford relaxes all edges, V-1 times, in any order

Dijkstra's careful ordering is what makes it fast but also what makes it fragile. Bellman-Ford's brute-force approach is slower but bulletproof.

The Bellman-Ford algorithm has a rich history, named after two pioneers who independently developed the core ideas:

Richard Bellman (1958):

Bellman was a mathematician working on dynamic programming—a paradigm he essentially invented. He recognized that shortest path problems exhibit optimal substructure: the shortest path to a vertex consists of the shortest path to its predecessor plus one edge. His formulation expressed shortest paths as a system of recursive equations (Bellman equations), solved iteratively.

Lester Ford Jr. (1956):

Ford, working at the RAND Corporation, developed equivalent ideas in the context of network flow problems. His contribution emphasized the algorithmic, step-by-step procedure rather than the mathematical formulation.

Edward F. Moore (1957):

Moore also made contributions to the algorithm, which is why it's sometimes called the Bellman-Ford-Moore algorithm. Moore was particularly focused on the queue-based optimization that is now called SPFA (Shortest Path Faster Algorithm).

The algorithm predates Dijkstra's (1959) by a few years. Interestingly, Dijkstra's algorithm became more famous for everyday use cases despite coming later, while Bellman-Ford retained importance for its broader applicability and theoretical significance in dynamic programming and optimization.

Negative edges are one thing; negative cycles are another—and far more problematic.

What is a negative cycle?

A negative cycle is a cycle (a path that starts and ends at the same vertex) whose total edge weight is negative. For example:

A --(-1)--> B --(-2)--> C --(2)--> A

Cycle: A → B → C → A with total weight = -1 + (-2) + 2 = -1

This is a negative cycle because the sum is negative.

Why negative cycles are catastrophic:

If a negative cycle is reachable from the source, the concept of 'shortest path' becomes undefined. Why? Because you can traverse the negative cycle infinitely and make the path length arbitrarily negative:

• Path with 0 cycle traversals: some finite cost
• Path with 1 cycle traversal: cost - 1
• Path with 2 cycle traversals: cost - 2
• Path with n cycle traversals: cost - n → -∞

No shortest path exists—you can always find a shorter one by looping more times.

Bellman-Ford's Superpower: Negative Cycle Detection

One of Bellman-Ford's key advantages is its ability to detect negative cycles. The algorithm runs V-1 iterations, which is guaranteed sufficient if no negative cycles exist. A V-th iteration is then performed:

• If any edge can still be relaxed in the V-th iteration, a negative cycle exists
• Because honest shortest paths have at most V-1 edges, finding an improvement after V-1 iterations means we're exploiting a cycle

This detection is both elegant and practically essential. In the currency arbitrage example, detecting a negative cycle means detecting profit opportunity. In network routing, it might indicate a configuration error creating routing loops.

What if the cycle can't reach my destination?

Importantly, a negative cycle only invalidates shortest paths to vertices reachable from that cycle. If the cycle is in a disconnected part of the graph, or can't reach your destination, shortest paths to your destination may still be well-defined. Sophisticated implementations can distinguish these cases.

We've established the critical context for understanding the Bellman-Ford algorithm:

What's Next:

Now that we understand why we need Bellman-Ford, we'll dive into how it works. The next page explores the algorithm's core mechanism: the relaxation process applied systematically over V-1 iterations, building shortest-path distances from the ground up.