Case Study: Building an Arbitrage Detector with Bellman-Ford

DataField.Dev

Case Study: Building an Arbitrage Detector with Bellman-Ford

"A program is correct when you can explain why it works — to a skeptic."

Executive Summary

In this build-focused case study you will construct, piece by piece, a small tool that scans a table of currency exchange rates and answers one question: is there a sequence of trades that turns money into more money out of thin air? That is arbitrage, and detecting it is one of the cleanest real uses of the machinery in §29.4. The trick is a change of weights — replace each exchange rate $r$ by $-\log r$ — that turns "a cycle whose rates multiply to more than 1" into "a cycle whose weights sum to less than 0," i.e. a negative cycle. You will then build Bellman-Ford from scratch, add the detector pass that finds the negative cycle, and finally reconstruct the actual trade loop, not just a yes/no answer. By the end you will have a working detector and a clear account of why every step is correct — including the one place the whole thing would silently break.

Skills applied

Translating a multiplicative real-world objective into the additive form shortest-path algorithms need (§29.1 modeling; §29.4 negative cycles).
Implementing Bellman-Ford from scratch, including the $|V|-1$ passes and the detector pass (§29.4).
Recovering a negative cycle from predecessor pointers, not merely detecting one (§29.4).
Reasoning carefully about floating-point and about why Dijkstra is the wrong tool here (§29.2, §29.4).

Background

The scenario

A fintech analyst maintains a matrix of best-available exchange rates between a handful of currencies. Each directed edge $u \to v$ carries a rate $r_{uv} > 0$: one unit of currency $u$ buys $r_{uv}$ units of $v$. A trade cycle — say USD → EUR → GBP → USD — multiplies its rates; if that product exceeds $1$, you end the loop with more USD than you started with, having taken no risk and added no value. That is an arbitrage opportunity, and in real markets it appears for fractions of a second before traders close it. The analyst wants a tool: feed it the rate table, and have it report whether arbitrage exists and, if so, which loop of trades realizes it.

Here is the rate table we will build against (a small, deliberately rigged market):

from \ to	USD	EUR	GBP
USD	—	0.90	0.75
EUR	1.10	—	0.84
GBP	1.40	1.20	—

🧩 Productive Struggle: Before reading on, try one loop by hand. Start with 1 USD, go USD → EUR → GBP → USD: multiply $0.90 \times 0.84 \times 1.40$. Is the result more or less than 1? Hold that number; we will recover exactly this cycle from the algorithm in Phase 4.

Why this matters — and why Dijkstra is the wrong tool

This is the canonical setting where Dijkstra cannot help. Arbitrage is precisely a negative cycle after the log transform, and §29.4 showed two things about negative cycles: Dijkstra can return wrong answers when negatives are present, and Bellman-Ford is the algorithm that not only tolerates negative edges but detects the negative cycles that make "shortest path" meaningless. Detecting arbitrage is detecting a negative cycle — so this case study is Bellman-Ford's reason to exist, made concrete.

Phase 1: From rates to weights — the log transform

Shortest-path algorithms add weights along a path; exchange rates multiply along a trade loop. We need a bridge. The logarithm is exactly the function that turns products into sums: $\log(xy) = \log x + \log y$.

Define the weight of edge $u \to v$ as $$w(u, v) = -\log r_{uv}.$$ Then for any cycle $v_0 \to v_1 \to \dots \to v_k \to v_0$, its total weight is $$\sum_{i} w(v_{i-1}, v_i) = -\sum_i \log r_{v_{i-1} v_i} = -\log\!\Big(\prod_i r_{v_{i-1} v_i}\Big).$$ Now read off the equivalence. The product of rates exceeds $1$ — an arbitrage — exactly when its logarithm is positive, exactly when the negated sum is negative: $$\prod_i r_{v_{i-1} v_i} > 1 \iff -\log\!\Big(\prod_i r\Big) < 0 \iff \text{the cycle has negative total weight.}$$ The minus sign is essential: it is what makes a profitable loop a negative cycle, which is the thing Bellman-Ford's detector finds.

import math

rates = {
    "USD": {"EUR": 0.90, "GBP": 0.75},
    "EUR": {"USD": 1.10, "GBP": 0.84},
    "GBP": {"USD": 1.40, "EUR": 1.20},
}

def build_edges(rates):
    """Turn a rate table into (u, v, weight) triples with weight = -log(rate)."""
    edges = []
    for u in rates:
        for v, r in rates[u].items():
            edges.append((u, v, -math.log(r)))
    return edges

vertices = list(rates)
edges = build_edges(rates)
# Spot-check the USD->EUR->GBP->USD loop weight by hand:
loop = -math.log(0.90) - math.log(0.84) - math.log(1.40)
print(round(loop, 4))            # = -log(0.90*0.84*1.40) = -log(1.0584)
print(round(0.90 * 0.84 * 1.40, 4))
# Expected output:
# -0.0568
# 1.0584

The loop USD → EUR → GBP → USD multiplies to $0.90 \times 0.84 \times 1.40 = 1.0584 > 1$: a 5.84% profit per lap. Its weight is $-\log(1.0584) \approx -0.0568 < 0$ — a negative cycle. (We computed $\log(1.0584) \approx 0.0568$ by hand from the rate product; the sign flip is the transform doing its job.) The arbitrage is real, and it is now visible to a negative-cycle detector.

💡 Intuition: Think of $-\log r$ as the "cost" of a trade in a currency where profit is cheap. A favorable trade ($r > 1$) has negative cost; an unfavorable one ($r < 1$) has positive cost. A loop you can traverse for negative total cost is a money pump — precisely a negative cycle.

Phase 2: Build Bellman-Ford from scratch

We need single-source shortest paths that tolerate negative edges, so Dijkstra is out and Bellman-Ford is in. Build it exactly as §29.4 describes: initialize, relax all edges $|V| - 1$ times, then one extra detector pass. We will track predecessors from the start, because Phase 4 needs them to rebuild the cycle. To make sure every vertex (and thus every possible arbitrage loop) is reachable, we use a standard trick: add a virtual source with a 0-weight edge to every currency.

INF = float("inf")

def bellman_ford(vertices, edges, source):
    """Returns (dist, prev). dist[v] is the shortest distance source->v;
    prev[v] is v's predecessor on a shortest path. Does NOT yet report cycles."""
    dist = {v: INF for v in vertices}
    prev = {v: None for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):           # |V| - 1 relaxation passes
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v], prev[v] = dist[u] + w, u
    return dist, prev

This is the workhorse. It is the same code from §29.4 with a prev array threaded through every relaxation — the identical predecessor-recording trick used for Dijkstra path recovery in §29.2. Note the guard dist[u] != INF: relaxing out of an unreached vertex (distance $\infty$) is meaningless and would corrupt arithmetic, so we skip it.

⚠️ Common Pitfall: It is tempting to "optimize" by stopping early the first pass that makes no changes. That early-exit is a valid speedup for the no-negative-cycle case — but if you also rely on "a change happened on pass $|V|$" to mean "negative cycle," you must be careful: the clean, unambiguous signal is a separate detector pass run after exactly $|V| - 1$ passes (next phase), not "did the last ordinary pass change anything." Keep detection separate from the main loop.

Phase 3: Add the detector pass

After $|V| - 1$ passes, every shortest distance is final if and only if there is no negative cycle reachable from the source (§29.4, path-relaxation property). So run all edges one more time: if any edge can still be relaxed, a reachable negative cycle exists — an arbitrage. We return the edge that relaxed, because its endpoint sits on (or downstream of) the offending cycle, which we will exploit in Phase 4.

def find_arbitrage(rates):
    """Return a vertex lying on a reachable negative cycle, or None if none."""
    vertices = ["__src__"] + list(rates)
    edges = build_edges(rates)
    edges += [("__src__", v, 0.0) for v in rates]   # virtual source reaches all
    dist, prev = bellman_ford(vertices, edges, "__src__")
    for u, v, w in edges:                            # the detector pass
        if dist[u] != INF and dist[u] + w < dist[v]:
            return v, prev                            # v is reachable from a neg cycle
    return None, prev

hit, prev = find_arbitrage(rates)
print(hit is not None)
print(hit)
# Expected output:
# True
# EUR

The detector fires: some edge still relaxes after $|V| - 1$ passes, so a negative cycle — an arbitrage — exists. The returned vertex (here EUR, the endpoint of the still-relaxable edge) is our handle on the cycle. The exact vertex depends on edge order, but any returned vertex is guaranteed to be reachable from a negative cycle, which is all Phase 4 needs.

🔄 Check Your Understanding Why do we add a virtual source "__src__" with 0-weight edges to every currency, rather than just picking, say, USD as the source?

Answer

Bellman-Ford only detects negative cycles reachable from the source. If we started at USD and some arbitrage loop happened to be unreachable from USD, we would miss it. A virtual source with a 0-weight edge to every vertex makes every currency (and thus every possible loop) reachable, so no arbitrage can hide. The 0-weight edges add no cost and cannot themselves create a cycle (nothing points back to the virtual source).

Phase 4: Reconstruct the trade loop

A yes/no answer is not actionable; a trader needs the sequence of trades. We recover the cycle from the predecessor pointers. Standard technique: starting from the flagged vertex, walk predecessors $|V|$ times to guarantee we land on the cycle (not merely on a path leading into it), then walk predecessors again until we revisit that vertex, collecting the loop.

def recover_cycle(hit, prev, n):
    """Walk predecessors to extract the vertices of a negative cycle."""
    cur = hit
    for _ in range(n):            # step n times to ensure we're inside the cycle
        cur = prev[cur]
    start = cur
    cycle = [start]
    cur = prev[start]
    while cur != start:           # collect until we loop back to start
        cycle.append(cur)
        cur = prev[cur]
    cycle.append(start)
    return cycle[::-1]            # reverse to forward trade order

hit, prev = find_arbitrage(rates)
cycle = recover_cycle(hit, prev, len(rates))
print(cycle)
# Expected output:
# ['USD', 'EUR', 'GBP', 'USD']

There it is — the actual money pump: USD → EUR → GBP → USD, the very loop we priced by hand in Phase 1 at a 5.84% per-lap profit. The tool now reports not just that arbitrage exists but exactly how to perform it. Let us confirm the profit by replaying the recovered cycle through the original rates (closing the loop, untransformed):

def cycle_profit(rates, cycle):
    """Multiply the rates around the recovered cycle; >1 means arbitrage."""
    product = 1.0
    for u, v in zip(cycle, cycle[1:]):
        product *= rates[u][v]
    return product

print(round(cycle_profit(rates, ["USD", "EUR", "GBP", "USD"]), 4))
# Expected output:
# 1.0584

The product is $1.0584 > 1$: starting with 1 USD and trading around the loop returns about 1.0584 USD. The detector's negative cycle and the market's arbitrage are the same fact, viewed through the $-\log$ transform.

🔗 Connection. Recovering the cycle here is the mirror image of recovering a shortest path in §29.2: both walk the prev array backward. The only twist is the "step $|V|$ times first" move, which guarantees you are standing on the cycle before you start collecting — a path leading into a cycle has a definite start, but the cycle itself has none.

Phase 5: Stress-test the boundaries

A correct tool must behave on the cases that are not arbitrage, too. Reason through two by hand.

First, a market with no arbitrage. Suppose every loop multiplies to at most 1 — e.g. perfectly consistent rates where $r_{uv} = 1 / r_{vu}$ and all triangles close exactly. Then every cycle's weight is $\ge 0$, the detector pass finds nothing relaxable, and find_arbitrage returns None. The tool correctly stays silent.

no_arb = {                       # consistent: USD/EUR = 0.9, EUR/USD = 1/0.9, etc.
    "USD": {"EUR": 0.90},
    "EUR": {"USD": 1.0 / 0.90},  # exactly inverse: loop product = 1, weight = 0
}
hit, _prev = find_arbitrage(no_arb)
print(hit)
# Expected output:
# None

The loop USD → EUR → USD multiplies to $0.90 \times (1/0.90) = 1$ exactly — weight $0$, not negative — so no arbitrage, and the detector returns None. (The boundary case "product exactly 1" is correctly treated as not profitable, because the detector tests strict <.)

⚠️ Common Pitfall (floating point). With real, noisy rate data, a loop that mathematically equals 1 may compute to weight $-10^{-16}$ from rounding, and the strict < could falsely flag arbitrage. A production detector uses a small tolerance, relaxing only when dist[u] + w < dist[v] - eps. We omit the tolerance here for clarity, but flag it: this is the realistic failure mode of the tool, and it is a numerical issue, not an algorithmic one. The algorithm is correct; the arithmetic needs care.

Second, the two-currency sanity check from §29.4's spirit: a single pair whose round-trip beats 1.

two = {"X": {"Y": 1.0}, "Y": {"X": 1.05}}   # X->Y->X = 1.05 > 1: arbitrage
hit, _prev = find_arbitrage(two)
print(hit is not None)
# Expected output:
# True

The loop X → Y → X multiplies to $1.05 > 1$ — weight $-\log(1.05) < 0$ — and the detector fires. The tool scales from the textbook two-vertex example up to the three-currency market without changing a line.

Discussion Questions

Why not Dijkstra? Spell out, in two sentences, why Dijkstra cannot be used for this task even after the log transform — citing both the presence of negative weights and the specific thing Bellman-Ford does that Dijkstra cannot (§29.4).
Tightness of $|V| - 1$. The analyst proposes running only $|V| - 2$ passes "to save time." Give a small market where a true shortest distance needs all $|V| - 1$ passes to settle, and explain what could go wrong with the truncated version (connect to §29.4's path-relaxation property).
Reading the sign. If you had used $w(u, v) = +\log r_{uv}$ (no minus sign) instead, what would an arbitrage cycle look like — positive or negative weight — and why would Bellman-Ford's detector (which tests for further decrease) then fail to find it?
Complexity. With $C$ currencies and a fully connected rate table, how many edges are there, and what is the tool's running time in terms of $C$? Tie your answer to Bellman-Ford's $O(VE)$ bound (§29.4) and to Chapter 14's Big-O reasoning.
Cost of the cycle. The recovered cycle has the most negative total weight only by luck of edge order; Bellman-Ford finds a negative cycle, not the most profitable one. Why does "find any negative cycle" suffice for an arbitrage detector, and what extra work would finding the most-profitable loop require?

Your Turn: Extensions

Option A (profit threshold). Real desks ignore arbitrage below a transaction-cost threshold. Modify the detector to relax only when dist[u] + w < dist[v] - eps for a small eps, and explain (using Phase 5's floating-point pitfall) how this both suppresses spurious flags and enforces a minimum profit.
Option B (best entry currency). Once arbitrage is found, the trader wants the loop expressed starting from a currency they actually hold (say USD). Modify recover_cycle to rotate the returned cycle so it begins at a chosen vertex, and verify the product is unchanged.
Option C (no-arbitrage certificate). When the detector returns None, the final dist array is a set of consistent "prices." Argue that dist then certifies no arbitrage exists (every edge satisfies $\text{dist}[u] + w \ge \text{dist}[v]$), and write a checker that verifies this certificate. This is the same "verify the witness" idea you will meet for NP problems in Chapter 37.
Option D (Toolkit tie-in). This chapter's Toolkit increment is dijkstra; the code/ folder also ships bellman_ford. Refactor your detector to call the Toolkit's bellman_ford rather than a local copy, keeping the signature stable, so a later chapter could reuse it.

Key Takeaways

Transform the objective to fit the tool. Shortest-path algorithms add; rates multiply. The $w = -\log r$ transform converts "product $> 1$" into "negative cycle," letting an off-the-shelf algorithm solve a problem it was not obviously built for (§29.1, §29.4).
Bellman-Ford detects what Dijkstra cannot. Negative edges and negative-cycle detection are exactly its job; arbitrage is the textbook negative cycle made real (§29.4).
Detection and reconstruction are different steps. The detector pass says whether a negative cycle exists; walking the prev array (after stepping $|V|$ times) says which loop it is — turning a yes/no into an actionable trade sequence.
The algorithm is exact; the arithmetic is not. The one way this correct tool silently fails is floating-point rounding near a product of exactly 1 — a numerical issue solved with a tolerance, not an algorithmic flaw. Naming the failure mode is part of building it correctly.