# Bellman-Ford Algorithm: How Traders Find Free Money with Graph Theory

> How the Bellman-Ford algorithm detects negative cycles in graphs and enables currency arbitrage for finding risk-free profit.

- Author: Shawn Ng (https://shawnng.com/about)
- Published: 2026-01-17
- Updated: 2026-09-30
- Canonical URL: https://shawnng.com/posts/bellman-ford-arbitrage
- Topics: algorithms, bellman-ford, arbitrage, graph-theory

## Key takeaways

- Bellman-Ford's real superpower is detecting negative cycles in a graph, which is exactly what a currency arbitrage opportunity is.
- Taking the negative logarithm of each exchange rate turns multiplicative rates into additive weights, making arbitrage a shortest-path problem.
- Bellman-Ford runs in O(V * E) time, so 150 actively traded currencies work out to roughly 3.4 million operations.
- Dijkstra cannot be used here because it fails on negative edge weights and has no mechanism for detecting negative cycles.
- Real systems must subtract transaction costs from edge weights, because a 0.1% profit disappears when each conversion costs 0.05%.

There is an algorithm from the 1950s that can detect opportunities to turn $1,000 into $1,008.50 with zero risk, just by exchanging currencies in the right order. It is called **Bellman-Ford**, and while most computer science students learn it as a shortest-path algorithm, its real superpower is detecting **negative cycles** in graphs. That is exactly what currency arbitrage is.

Check out the full video on my YouTube channel [Divide and Quantum](https://www.youtube.com/watch?v=0n8ZwXDKwcw).

## What Is Currency Arbitrage?

Currency arbitrage exploits inconsistencies in exchange rates. Suppose you have three currencies with these rates:

- 1 USD = 0.92 EUR
- 1 EUR = 130.5 JPY
- 1 JPY = 0.0084 USD

If you start with $1,000 and follow the chain:

1. $1,000 -> 920 EUR
2. 920 EUR -> 120,060 JPY
3. 120,060 JPY -> $1,008.50

You end up with $1,008.50. That is $8.50 of profit from a round trip through three currencies. No speculation, no risk, just a mathematical inconsistency in the rates.

In practice, these opportunities are tiny and vanish within milliseconds. But for high-frequency trading firms processing billions of dollars, even fractions of a cent per transaction add up. The question is: how do you find these opportunities algorithmically?

## Turning Exchange Rates Into a Graph Problem

The trick is to model currencies as nodes in a directed graph, where each edge weight represents an exchange rate. But there is a catch: we need to convert this into a shortest-path problem, and exchange rates are multiplicative, not additive.

The solution is to take the **negative logarithm** of each exchange rate. Here is why that works:

- Multiplying exchange rates along a path: `rate_1 * rate_2 * rate_3`
- Taking the log converts multiplication to addition: `log(rate_1) + log(rate_2) + log(rate_3)`
- Negating it converts the problem to shortest path: `-log(rate_1) + -log(rate_2) + -log(rate_3)`

An arbitrage opportunity exists when the product of rates around a cycle is greater than 1. After our transformation, that same cycle has a **negative total weight**. Finding arbitrage is now equivalent to finding negative cycles in a graph, which is exactly what Bellman-Ford does.

## How Bellman-Ford Works

Bellman-Ford finds the shortest path from a source node to all other nodes in a weighted graph, even when edge weights are negative. Here is the algorithm at a high level:

1. Initialize the distance to all nodes as infinity, except the source (distance = 0).
2. Repeat V-1 times (where V is the number of vertices): for every edge (u, v) with weight w, if `distance[u] + w < distance[v]`, update `distance[v]`.
3. Do one more pass over all edges. If any distance can still be reduced, a negative cycle exists.

The key insight is step 3. In a graph with no negative cycles, the shortest path between any two nodes uses at most V-1 edges. So after V-1 relaxation passes, all distances should be final. If a V-th pass still finds improvements, it means there is a cycle where the total weight is negative, and you could keep going around it forever, reducing the "distance" infinitely.

### Time Complexity

Bellman-Ford runs in **O(V * E)** time, where V is the number of vertices and E is the number of edges. For a currency graph with N currencies, we have N vertices and up to N^2 edges (every currency can be exchanged for every other), giving us **O(N^3)** time. With around 150 actively traded currencies, that is roughly 3.4 million operations, trivially fast for a modern computer.

## Python Implementation

Here is a complete implementation that detects arbitrage opportunities:

```python
import math

def detect_arbitrage(currencies, rates):
    """
    Detect currency arbitrage using Bellman-Ford.

    currencies: list of currency names, e.g. ['USD', 'EUR', 'JPY', 'GBP']
    rates: 2D list where rates[i][j] is the exchange rate from
           currency i to currency j

    Returns: list of currency names forming an arbitrage cycle,
             or None if no arbitrage exists
    """
    n = len(currencies)

    # Transform rates: edge weight = -log(rate)
    graph = []
    for i in range(n):
        for j in range(n):
            if i != j:
                weight = -math.log(rates[i][j])
                graph.append((i, j, weight))

    # Bellman-Ford from node 0
    dist = [float('inf')] * n
    predecessor = [-1] * n
    dist[0] = 0

    # Relax edges V-1 times
    for _ in range(n - 1):
        for u, v, w in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                predecessor[v] = u

    # Check for negative cycles (V-th iteration)
    for u, v, w in graph:
        if dist[u] + w < dist[v]:
            # Negative cycle found: trace it back
            cycle = []
            visited = set()
            node = v

            # Walk back through predecessors to find the cycle
            for _ in range(n):
                node = predecessor[node]

            cycle_start = node
            current = cycle_start
            while True:
                cycle.append(currencies[current])
                current = predecessor[current]
                if current == cycle_start:
                    cycle.append(currencies[current])
                    break

            cycle.reverse()
            return cycle

    return None
```

And here is how you would use it:

```python
currencies = ['USD', 'EUR', 'GBP', 'JPY']

# Exchange rate matrix
# rates[i][j] = how much of currency j you get for 1 unit of currency i
rates = [
    #  USD     EUR     GBP     JPY
    [1.0,    0.92,   0.79,   149.5  ],  # USD
    [1.09,   1.0,    0.86,   162.5  ],  # EUR
    [1.27,   1.17,   1.0,    189.8  ],  # GBP
    [0.0067, 0.0062, 0.0053, 1.0    ],  # JPY
]

result = detect_arbitrage(currencies, rates)

if result:
    print(f"Arbitrage opportunity found: {' -> '.join(result)}")
else:
    print("No arbitrage opportunity detected.")
```

## Why Bellman-Ford Instead of Dijkstra?

This is a natural question. [Dijkstra's algorithm](https://shawnng.com/posts/dijkstras-algorithm-explained) is faster for shortest paths (O(E log V) vs O(V * E)). But Dijkstra has a fatal limitation: **it cannot handle negative edge weights**. Since our transformed exchange rates can be negative (any rate greater than 1 produces a negative log), Dijkstra simply does not work here.

More importantly, Dijkstra has no mechanism for detecting negative cycles. It assumes the shortest path is always well-defined. Bellman-Ford's "extra" relaxation pass is specifically designed to catch the case where shortest paths are not well-defined because you can keep reducing the cost forever. When weights are non-negative and you already know where the goal is, the faster tool is [A* pathfinding](https://shawnng.com/posts/astar-pathfinding-vs-dijkstra).

## From Theory to Trading Floors

Real-world arbitrage detection systems build on Bellman-Ford but add several layers:

### Speed Optimizations

Markets move in microseconds. Implementations use early termination (stop if no distances change in a pass), SPFA (Shortest Path Faster Algorithm, a queue-based variant of Bellman-Ford), and limit the search to recently updated exchange rates.

### Transaction Costs

Real exchanges charge fees. A 0.1% profit disappears fast when each conversion costs 0.05%. The algorithm must subtract transaction costs from edge weights before checking for negative cycles.

### Execution Risk

By the time you detect an arbitrage opportunity, compute the trade, and submit the orders, the rates may have changed. High-frequency trading firms co-locate their servers next to exchange servers to minimize latency, sometimes spending millions of dollars to shave off microseconds.

### Multi-Leg Arbitrage

The example above uses three currencies, but real opportunities often involve four, five, or more legs. Bellman-Ford naturally handles this since it checks all edges in each pass, regardless of cycle length.

## Beyond Currency Markets

Negative cycle detection has applications far beyond trading:

- **Supply chain optimization**: Finding cycles where shipping goods through intermediate warehouses is cheaper than direct routes.
- **Network routing**: Detecting routing loops in protocols that allow negative-cost links.
- **Game theory**: Finding infinite-reward cycles in reward graphs for reinforcement learning.

Once the question shifts from finding a cycle to minimising cost under constraints, the tool of choice becomes [linear programming and the simplex method](https://shawnng.com/posts/linear-programming-routes-the-world).

## Key Takeaways

Bellman-Ford is often overlooked in favor of Dijkstra, but its ability to handle negative weights and detect negative cycles makes it uniquely powerful. Currency arbitrage is the most dramatic example: by transforming exchange rates with a negative logarithm, we convert a financial problem into a graph theory problem and solve it with an algorithm Ford and Bellman published in 1956 and 1958. The math has not changed. The speed at which it is executed has.

## Frequently asked questions

### What does the Bellman-Ford algorithm do that Dijkstra cannot?

Bellman-Ford handles negative edge weights and detects negative cycles. Dijkstra assumes a shortest path is always well-defined and breaks on negative weights, with no way to report that a negative cycle exists.

### What is the time complexity of Bellman-Ford?

O(V * E), where V is the number of vertices and E is the number of edges. A currency graph with N currencies has N vertices and up to N^2 edges, which makes the run O(N^3).

### How do you detect currency arbitrage with a graph algorithm?

Model each currency as a node and each exchange rate as an edge weighted by the negative logarithm of that rate. A cycle whose rates multiply to more than 1 becomes a negative-weight cycle, which the extra relaxation pass in Bellman-Ford detects.

### Is currency arbitrage still profitable?

The opportunities are tiny and vanish within milliseconds, so they only pay at high-frequency scale. Transaction costs can erase the profit entirely, and firms co-locate servers next to exchanges to cut the latency between detection and execution.

## Sources

- Richard Bellman (1958). [On a routing problem](https://doi.org/10.1090/qam/102435). Quarterly of Applied Mathematics.
- L. R. Ford (1956). [Network Flow Theory](https://www.rand.org/pubs/papers/P923.html). RAND Corporation (Paper P-923).
- E. W. Dijkstra (1959). [A note on two problems in connexion with graphs](https://doi.org/10.1007/BF01386390). Numerische Mathematik.