Bellman-Ford From Zero: Finding a Negative Cycle

Lesson 6 of the course "Build your own arbitrage bot". In lesson 5 a profitable circle became a circle whose weights add up to less than zero. Today you learn the classic algorithm that finds such a circle.

First, try it head-on

Before any clever algorithm, solve the problem the blunt way and see where it hurts. Try every possible circle, multiply the rates, and keep the best one.

import itertools

rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75}

def brute(rates, max_len):
    nodes = sorted({n for edge in rates for n in edge})
    best, tried = (1.0, None), 0
    for k in range(2, max_len + 1):
        for path in itertools.permutations(nodes, k):
            tried += 1
            cycle = list(path) + [path[0]]
            money = 1.0
            for a, b in zip(cycle, cycle[1:]):
                if (a, b) not in rates:
                    money = None
                    break
                money *= rates[(a, b)]
            if money and money > best[0]:
                best = (money, cycle)
    return best, tried

print(brute(rates, 3))

Output:

((1.0296, ['EUR', 'GBP', 'USD', 'EUR']), 12)

It works: the same circle, the same 1.0296, after 12 tries. Now make the market bigger. With every currency tradable against every other (a worst case, but close to a big exchange), these are the counts and times I measured on one laptop:

Each new currency multiplies the work by about ten. At 15 currencies you would wait days, and a real exchange has hundreds. The blunt method is correct and useless. You also see why: it checks the same partial paths again and again. The rest of this lesson is a method that remembers what it already learned.

The idea in plain words

Imagine a map of cities joined by one-way roads, and each road has a cost. You stand in city S and want to know the cheapest way to every other city. Your first guess is "I do not know yet", which you write as infinity. Then you improve your guesses again and again.

An improvement works like this. Look at one road from city A to city B with cost w. If the cheapest known way to A, plus w, is cheaper than what you know for B, you have found a better way to B. Write the new number. That step is called relaxing the road.

Bellman-Ford simply relaxes every road, again and again, until nothing improves.

A worked example

Three cities S, A, B and three roads: S to A costs 4, S to B costs 5, A to B costs −2. (A negative cost is allowed: think of a discount.)

Start: S = 0, A = ∞, B = ∞.

Round 1, going through the roads in the order S to A, S to B, A to B:

• S to A: 0 + 4 = 4 is better than ∞, so A = 4.
• S to B: 0 + 5 = 5 is better than ∞, so B = 5.
• A to B: 4 + (−2) = 2 is better than 5, so B = 2.

Round 2: nothing improves. We stop. Cheapest ways: A costs 4, B costs 2 (the way S, A, B).

How many rounds can be needed? A cheapest way never visits a city twice, so with V cities it uses at most V − 1 roads. Each round extends the correct information by at least one road, so V − 1 rounds are always enough.

The extra round: how a negative cycle shows up

Suppose a circle of roads has a total cost below zero. Every time you go around it, the numbers get smaller, forever. So the improvements never stop.

Bellman-Ford uses this. It runs the V − 1 normal rounds, then does one more round. If any road still improves, a negative cycle exists. If nothing improves, there is none.

Tiny example with the circle from lesson 5. Take weights USD to EUR +0.1054, EUR to GBP +0.1278, GBP to USD −0.2624. Their sum is −0.0292. Start at USD with 0.

• Round 1: EUR = 0.1054, GBP = 0.2332, then GBP to USD gives 0.2332 − 0.2624 = −0.0292, better than 0, so USD = −0.0292.
• Round 2: EUR = −0.0292 + 0.1054 = 0.0762, GBP = 0.2040, USD = −0.0584.
• It keeps going down, by 0.0292 per lap.

With three nodes we need at most 2 normal rounds, and the extra round (round 3) still improves something. That is the alarm.

Getting the circle itself

An alarm is not yet a circle. For each node we remember the node we came from, called its predecessor. When the extra round improves some node, we follow predecessors backward. After V steps we are certain to be inside the circle (a path of V steps over V nodes must repeat a node). Then we walk the circle until we return to where we started.

The code

import math

rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75}
nodes = ["USD", "EUR", "GBP"]
edges = [(a, b, -math.log(r)) for (a, b), r in rates.items()]

def bellman_ford(nodes, edges, start):
    dist = {n: math.inf for n in nodes}
    prev = {n: None for n in nodes}
    dist[start] = 0.0
    for _ in range(len(nodes) - 1):          # the V - 1 normal rounds
        changed = False
        for a, b, w in edges:
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                prev[b] = a
                changed = True
        if not changed:
            break
    for a, b, w in edges:                    # the extra round
        if dist[a] + w < dist[b]:
            prev[b] = a
            x = b
            for _ in range(len(nodes)):      # step back V times: now inside the cycle
                x = prev[x]
            cycle, y = [x], prev[x]
            while y != x:
                cycle.append(y)
                y = prev[y]
            cycle.reverse()
            return cycle + [cycle[0]]
    return None

cycle = bellman_ford(nodes, edges, "USD")
print("cycle:", cycle)
money = 1.0
for a, b in zip(cycle, cycle[1:]):
    money *= rates[(a, b)]
print("1 unit becomes", round(money, 4))

Output:

cycle: ['GBP', 'USD', 'EUR', 'GBP']
1 unit becomes 1.0296

The program found the same circle as in lesson 5, starting from a different point of the circle (a circle has no beginning). The check at the end multiplies the real rates along the circle and gets 1.0296, the number we computed by hand.

How fast is it?

Each round looks at every road once, and there are at most V rounds, so the work is about V × E steps (E is the number of roads). For a market with 300 currencies and 1800 pairs, that is up to 540 thousand checks per scan. This is fine for a hobby bot and slow for one that must scan many times a second. Lesson 7 shows a trick that skips most of this work.

Honest warnings

• Bellman-Ford returns one negative cycle, not the best one.
• Rates move while you compute. The circle you find is a snapshot.
• It uses mid-market style rates: it does not know how much you can trade. That is stage 2 (lessons 9 and 10).

Let an AI agent write and test it

A vague request:

Implement Bellman-Ford to find arbitrage.

A request with a test inside:

Write bellman.py with a function find_cycle(rates) that takes a dictionary {("USD","EUR"): 0.90, ...}, converts rates to weights with minus natural log, runs Bellman-Ford with the extra round and predecessors, and returns the cycle as a list of currency names, or None. Add a test with these rates: USD to EUR 0.90, EUR to GBP 0.88, GBP to USD 1.30, EUR to USD 1.10, GBP to EUR 1.10, USD to GBP 0.75. The test must print the cycle and the money multiplier, which must be 1.0296. Add a second test with the rates all multiplied by 0.95: it must return None.

The second test matters. A program that always finds a cycle passes the first test too.

Your exercise

1. Run the code. Do you get the multiplier 1.0296?
2. Multiply every rate by 0.95 (a big fee). Run again. You should get None. Why? The circle product is 1.0296 × 0.95³ = 0.883, below 1.
3. By hand: three cities S, A, B with roads S to A 4, S to B 5, A to B −2. Do the rounds on paper, and then check them with a small code snippet.
4. Find out how many rounds the normal part needs for this graph before it stops. Add a counter.

What comes next

Bellman-Ford rechecks all roads every round, even those that cannot have changed. Lesson 7 shows SPFA, a lazy version that only rechecks the roads that start at a node that just improved.