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

There is an algorithm from the 1950s that can detect opportunities to turn $1,000 into $1,005 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.

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 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.

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.

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 published in 1958. The math has not changed. The speed at which it is executed has.