SPFA From Zero: The Lazy Version of Bellman-Ford

Lesson 7 of the course "Build your own arbitrage bot". In lesson 6 you built Bellman-Ford. It works, but it wastes effort. Today you make it lazy.

Where Bellman-Ford wastes work

Bellman-Ford from lesson 6 is the head-on version of this lesson: recheck everything, every round, and be sure. We keep it as the reference, because any faster method must give the same answers.

Bellman-Ford checks every road in every round. But a road from A to B can only give a better way to B if the number at A has just become smaller. If A did not change since the last time you looked at its roads, looking again changes nothing.

Picture a teacher who rechecks all 30 homework notebooks every day, even though only three students handed in something new. A lazier and smarter teacher keeps a list of "students who changed something" and checks only those. That list is the whole idea of SPFA (the Shortest Path Faster Algorithm).

The idea

1. Keep a queue: a line of nodes that have to be processed. Nodes join at the back and leave from the front.
2. Start with only the start node in the queue.
3. Take the front node A out. For each road from A to some B, try to relax it (is the number at A plus the cost better than the number at B?).
4. If B improved and B is not already waiting in the queue, put B at the back.
5. Repeat until the queue is empty.

If the queue empties, every number is final.

A worked example

Same roads as in lesson 6: S to A costs 4, S to B costs 5, A to B costs −2.

Start: S = 0, A = ∞, B = ∞. Queue: [S].

• Take S. Road S to A: 0 + 4 = 4 < ∞, so A = 4, A joins the queue. Road S to B: 0 + 5 = 5 < ∞, so B = 5, B joins the queue. Queue: [A, B].
• Take A. Road A to B: 4 − 2 = 2 < 5, so B = 2. B is already in the queue, so we do not add it again. Queue: [B].
• Take B. B has no roads out. Queue: [].

Done after checking 3 roads. Bellman-Ford would have checked 3 roads in round 1 and 3 in round 2 to be sure: 6 checks. Here SPFA did half the work.

What about negative cycles?

If a negative cycle is reachable, some nodes keep improving and keep re-entering the queue forever. The program would never stop. We need an alarm.

The alarm: count how many times each node has entered the queue. In a graph without negative cycles, a node enters at most V − 1 times (the cheapest way to it uses at most V − 1 roads, and each entry corresponds to a new, longer way). So if a node enters V times, there is a negative cycle through it.

The code

import math
from collections import deque

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"]
out = {n: [] for n in nodes}                       # roads leaving each node
for (a, b), r in rates.items():
    out[a].append((b, -math.log(r)))

def spfa(nodes, out, start):
    dist = {n: math.inf for n in nodes}
    prev = {n: None for n in nodes}
    entered = {n: 0 for n in nodes}                # how many times n joined the queue
    dist[start] = 0.0
    queue, waiting = deque([start]), {start}
    checks = 0
    while queue:
        a = queue.popleft()
        waiting.discard(a)
        for b, w in out[a]:
            checks += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                prev[b] = a
                if b not in waiting:
                    entered[b] += 1
                    if entered[b] >= len(nodes):   # the alarm
                        return ("negative cycle through", b, "after", checks, "checks")
                    queue.append(b)
                    waiting.add(b)
    return ("no negative cycle", {n: round(d, 4) for n, d in dist.items()}, checks)

print(spfa(nodes, out, "USD"))

Output:

('negative cycle through', 'EUR', 'after', 13, 'checks')

SPFA raised the alarm. To get the circle itself, use the predecessors the same way as in lesson 6: step back from the alarmed node V times, then walk the circle. Try it as an exercise.

Speed: a test you can run

Here is a market with 300 currencies, each with 6 random pairs. The rates are made from hidden true values with a 0.2 percent fee on every trade, so no circle is profitable (a calm market). We count the road checks from the same start.

import math, random
from collections import deque
random.seed(1)
N = 300
nodes = list(range(N))
value = [random.uniform(1, 100) for _ in nodes]
edges, out = [], {n: [] for n in nodes}
for a in nodes:
    for b in random.sample(nodes, 6):
        if a != b:
            w = -math.log(value[a] / value[b] * 0.998)
            edges.append((a, b, w)); out[a].append((b, w))

def bf_work():
    dist = [math.inf] * N; dist[0] = 0.0; work = 0
    for _ in range(N - 1):
        changed = False
        for a, b, w in edges:
            work += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w; changed = True
        if not changed: break
    return work

def spfa_work():
    dist = [math.inf] * N; dist[0] = 0.0; work = 0
    q, inq = deque([0]), {0}
    while q:
        a = q.popleft(); inq.discard(a)
        for b, w in out[a]:
            work += 1
            if dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                if b not in inq: q.append(b); inq.add(b)
    return work

print("edges:", len(edges), "Bellman-Ford checks:", bf_work(), "SPFA checks:", spfa_work())

Output of a test run:

edges: 1799 Bellman-Ford checks: 7196 SPFA checks: 1799

SPFA did a quarter of the work here. In practice SPFA tends to be much faster on sparse graphs, which crypto markets are (each coin trades against a few others). But the worst case of SPFA is as bad as Bellman-Ford's, V × E, and rare graphs can trigger it. The speed-up depends on the shape of the data, so measure on your own data.

When to use which

Let an AI agent write and test it

A vague request:

Make Bellman-Ford faster.

A request that names the technique and the check:

In bellman.py add spfa_find_cycle(rates) using a queue, an "in queue" set, a count of how many times each node entered the queue, and predecessors. It must return the same cycle as find_cycle on the six-rate example, and None when all rates are multiplied by 0.95. Then write bench.py that builds a random market of 300 currencies with 6 pairs each (rates from hidden values times 0.998), counts road checks for both algorithms from node 0, and prints both numbers. Do not change find_cycle.

You should see SPFA with fewer checks. If the agent shows SPFA with more checks on that data, ask it to explain why, and do not accept "the algorithm is better in theory" as an answer.

Your exercise

1. Run the first program. Make it return the circle itself using predecessors.
2. Run the benchmark. Change the number of pairs per currency from 6 to 30. Does SPFA still win by the same factor? Why might a denser graph change the answer?
3. Change the fee factor 0.998 to 1.001 (a market with free money). Run the benchmark's spfa_work from node 0. It never stops, because it has no alarm. Stop it with Ctrl+C, then add the "entered V times" alarm from the first program and run it again. How many checks does it need before the alarm?
4. Save your code as a new version.

What comes next

Both algorithms answer "is there a profitable circle somewhere?". A real bot wants more: the best circle, with a limited number of steps, found again and again while prices change. Lesson 8 shows how a recent research algorithm, RICH, attacks that problem.