Routing Algorithms

ƒxyz Network routes FX conversions across a weighted directed graph where nodes are currencies and edges are exchange rate pairs. Three algorithms work in concert: Bellman-Ford finds optimal paths, the line-graph transformation improves routing on dense networks, and negative-cycle detection identifies arbitrage opportunities.

Implementation: packages/neo4j-network/src/services/routing-engine.ts GraphQL queries: findRoute, detectArbitrage, routingGraphInfo Paper references: C6, D6

Bellman-Ford Routing

Overview

Bellman-Ford finds the shortest (cheapest) path between any two currencies in the FX exchange graph. Unlike Dijkstra, Bellman-Ford handles negative edge weights - which is essential for arbitrage detection.

The routing engine converts exchange rates to log-space edge weights so that multiplicative rate chains become additive path weights:

edge weight w(u,v) = -log(rate(u → v))

A cheaper path (lower total weight) corresponds to a more favorable exchange rate sequence.

Algorithm

Initialize: d[source] = 0, d[v] = +inf for all other v
Repeat |V|-1 times:
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      d[v] = d[u] + w
      predecessor[v] = u

Arbitrage check (iteration |V|):
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      negative cycle detected → arbitrage opportunity

Complexity: O(|V| * |E|)

Mathematical Formulation

For an FX path through currencies c1 → c2 → ... → cn:

Total log-cost = sum(-log(rate(ci → ci+1)))
               = -log(product(rates along path))

Optimal path = argmin over all paths of total log-cost
             = argmax over all paths of product(exchange rates)

Implementation

// bellmanFord() in packages/neo4j-network/src/services/routing-engine.ts
bellmanFord(
  graph: Map<string, Map<string, number>>,
  source: string
): { distances: Map<string, number>; predecessors: Map<string, string> }

The function returns distances and predecessors for path reconstruction. The routing graph is built from live ECB FX rate data and crypto prices via buildRoutingGraph().

Line-Graph Transformation

Overview

The standard Bellman-Ford treats each currency node as the unit of routing. This ignores a real cost in FX trading: switching between currency pairs at an intermediate currency incurs spread costs that depend on which pair you came from and which pair you're entering.

The line-graph transformation (Paper D6) solves this by converting the FX graph into a line graph where edges become nodes. This allows edge-switching costs to be expressed as ordinary node weights, making the full bid-ask spread model compatible with standard shortest-path algorithms.

Transformation

Given the original FX graph G = (V, E):

Line graph L(G):
  Vertices of L(G) = edges of G
  Two vertices of L(G) are adjacent iff the corresponding
  edges of G share an endpoint (i.e., a currency hop)

For FX routing, this means:

• Each currency pair (e.g., EUR/USD) becomes a node in L(G)
• Adjacent nodes in L(G) share a common currency
• Edge weights in L(G) represent the cost of transitioning through that common currency (bid-ask spread, liquidity penalty)

Performance

Paper D6 reports that line-graph routing on dense FX networks achieves over 50% improvement in effective rate versus naive Bellman-Ford, because it properly accounts for spread accumulation at each currency hop.

Implementation

// buildLineGraph() in packages/neo4j-network/src/services/routing-engine.ts
buildLineGraph(edges: RouteEdge[]): {
  nodes: Map<string, LineGraphNode>;
  edges: LineGraphEdge[];
}

// Activated via useLineGraph parameter on findRoute query:
findRoute(from: "EUR", to: "JPY", useLineGraph: true)

Arbitrage Detection

Overview

In a correctly priced FX market, converting EUR → USD → JPY → EUR should return exactly the starting amount (minus spreads). When the product of exchange rates along a cycle exceeds 1.0, the cycle is profitable - a textbook arbitrage opportunity.

In the log-rate graph, this corresponds to a negative-weight cycle: a cycle where the sum of log-costs is negative.

Mathematical Formulation

For a cycle of currencies c1 → c2 → ... → cn → c1:

Profit = product(rate(ci → ci+1)) - 1
       = exp(-sum(log-weights along cycle)) - 1

Profitable cycle: sum(log-weights) < 0, which means product(rates) > 1.

After the standard |V|-1 Bellman-Ford relaxations, a |V|-th pass that still finds a shorter path indicates a negative cycle exists.

Algorithm

Run Bellman-Ford for |V|-1 iterations (standard shortest path)

On iteration |V|:
  For each edge (u, v, w):
    if d[u] + w < d[v]:
      v is in or reachable from a negative cycle
      → trace predecessor chain to extract the cycle
      → compute cycle profit
      → emit as arbitrage opportunity

Cycle Profit Calculation

// findNegativeCycles() in packages/neo4j-network/src/services/routing-engine.ts
findNegativeCycles(
  graph: Map<string, Map<string, number>>
): ArbitrageCycle[]

interface ArbitrageCycle {
  path: string[];          // e.g. ["EUR", "USD", "JPY", "EUR"]
  profitPercent: number;   // e.g. 0.12 for 0.12% profit
  rateProduct: number;     // product of exchange rates along cycle
}

Dijkstra Shortest Path

Overview

Dijkstra's algorithm finds the shortest path in a graph with non-negative edge weights by greedily expanding the lowest-cost frontier using a priority queue. In the currency routing demo visualization, Dijkstra provides the baseline shortest-path computation.

Limitation: Dijkstra cannot handle negative edge weights. Since the FX log-rate graph can produce negative weights (required for arbitrage detection), production routing uses Bellman-Ford. Dijkstra is used in the demo visualization and as a fast path for graphs known to have non-negative weights.

Algorithm

Initialize: d[source] = 0, d[v] = +inf for all other v
Priority queue Q with all vertices

While Q is not empty:
  u = extract-min(Q)
  For each neighbor v of u:
    if d[u] + w(u,v) < d[v]:
      d[v] = d[u] + w(u,v)
      predecessor[v] = u
      decrease-key(Q, v)

Complexity: O(|E| + |V| log |V|) with a Fibonacci heap.

A* Pathfinding

Overview

A* extends Dijkstra with a heuristic function h(v) that estimates the cost-to-goal, allowing the search to focus on promising directions. In the currency routing operational system, A* uses a route-scoring heuristic that accounts for fees, speed, and reliability.

Formula

f(v) = g(v) + h(v)

Where:
  g(v) = known cost from source to v
  h(v) = heuristic estimate from v to goal (must be admissible: h(v) <= true cost)
  f(v) = estimated total cost through v

The search expands the node with the lowest f(v) first. When h is admissible, A* is guaranteed to find the optimal path.

Triangular Arbitrage Detection

Overview

Triangular arbitrage is a special case of cyclic arbitrage restricted to 3-node cycles in the FX graph. A triangular arbitrage occurs when converting A to B to C to A yields more than the starting amount. This is detectable as a length-3 negative cycle in the log-rate graph.

Formula

Spread = r(A->B) * r(B->C) * r(C->A) - 1

In log-space:
  sum = -log(r(A->B)) + -log(r(B->C)) + -log(r(C->A))
  Profitable if sum < 0 (i.e., product of rates > 1)

Triangular arbitrage is the most commonly observed form in FX markets because 3-hop cycles execute fastest and face the least slippage.

Planned Extensions

STAP: Standardized Total Arbitrage Profit (Paper D6b, arXiv:2508.03217)

STAP extends the line-graph DEX routing framework by defining a standardized metric for total arbitrage profit across all possible cycles. STAP-maximizing execution provably eliminates all arbitrage opportunities in the graph:

STAP = sum over all negative cycles C: |profit(C)|

STAP provides a single scalar that quantifies the total inefficiency in the exchange graph. A STAP of zero means the market is in no-arbitrage equilibrium. Planned as an extension to routing-engine.ts.

Tropical Algebra Scanner (Paper C6)

Tropical (min-plus) algebra provides a unified algebraic framework for computing all shortest paths simultaneously. Planned tropicalArbitrageScan() in tropical-arbitrage.ts.

Genetic Algorithm Optimization (PaymentsCanada paper)

For large FX graphs (>100 currencies), exact cycle enumeration becomes expensive. Planned GA-based cycle optimizer in ga-arbitrage.ts uses evolutionary search to find high-profit cycles efficiently.

Paper References