Introduction

Modern electronic markets look less like a single venue and more like an archipelago of exchanges, dark pools, and liquidity providers. Posting or sweeping an order without considering this fragmentation invites higher spread, hidden fees, and slippage.

Smart Order Routers (SORs) aim to solve this by dynamically decomposing one parent order into many child routes across venues. In this article I’ll show how viewing the market as a weighted graph lets us apply Dijkstra’s shortest-path algorithm to find the cheapest path to fill an order, fast enough for real trading.

---

The Fragmented Marketplace Problem

An order of size $Q$ must be filled across $N$ distinct venues. Each venue $i$ quotes:

• Price $P_i$ (best bid/ask)
• Fee or rebate $F_i$
• Available depth $q_i \le Q$ (you may need multiple hops to satisfy the full size)

The naïve strategy, routing everything to the lowest quoted price, ignores rebates, hidden liquidity, and partial fills. We need a framework that captures all costs together.

---

Modelling Liquidity as a Graph

Define a directed graph $G = (V, E)$ where:

• Vertices V are liquidation states: the remaining quantity $Q_\text{left} \in \{0,1,\dots,Q\}$.
• Edges E represent child fills on a venue. Each edge $\bigl(Q_\text{left} \;\xrightarrow{\;i,\;q_i\;}\; Q_\text{left}-q_i\bigr)$ bears a weight (cost) $w_i(q_i)=q_i\,(P_i + F_i)\;.$

Finding the minimum-cost path from $Q_\text{left}=Q$ to $0$ is exactly a shortest-path problem.

---

Dijkstra’s Algorithm Refresher

Dijkstra’s algorithm finds the shortest paths from a source node to all others in a graph with non-negative weights. Its complexity is

using a binary heap priority queue, fast enough when $Q$ is small or the quantity discretisation is coarse.

---

Why Dijkstra Works for SOR

1. Non-negative edge weights, prices + fees are never negative.
2. Additive costs, total spend is the sum of individual fills.
3. Incremental updates, when a quote changes, only a handful of edges are updated; no need to rebuild the whole graph.

---

Edge Weights in Detail

A realistic cost function blends price, fee, slippage, and latency:

• $\sigma_i(q)$ – estimated impact cost for size $q$
• $L_i$ – round-trip latency to venue $i$
• $\lambda_s, \lambda_l$ – trader-defined risk aversion parameters.

By tuning $\lambda$-values the router can pivot between pure cost minimisation and fast execution.

---

A Minimal Python Sketch

import heapq
from collections import defaultdict

def dijkstra_sor(start_qty, venues):
    """
    venues: list of dicts {'name': str, 'price': float, 'fee': float, 'depth': int}
    start_qty: int
    """
    # state is remaining quantity
    dist = defaultdict(lambda: float('inf'))
    prev = {}
    dist[start_qty] = 0
    pq = [(0, start_qty)]

    while pq:
        cost, qty = heapq.heappop(pq)
        if qty == 0:
            break                          # finished
        for v in venues:
            fill = min(v['depth'], qty)
            nxt = qty - fill
            w = fill * (v['price'] + v['fee'])
            new_cost = cost + w
            if new_cost < dist[nxt]:
                dist[nxt] = new_cost
                prev[nxt] = (qty, v['name'], fill)
                heapq.heappush(pq, (new_cost, nxt))

    # Reconstruct route
    route, node = [], 0
    while node in prev:
        prev_node, venue, fill = prev[node]
        route.append((venue, fill))
        node = prev_node
    return list(reversed(route)), dist[0]

The sketch ignores slippage and latency penalties, but extending w to the full formula above is one line.

---

Real-Time Tweaks

• Streaming quotes → treat weight updates as decreases in Dijkstra’s heap; this costs $\mathcal{O}(\log V)$ per change.
• Incremental fills → after each child order, update $Q_\text{left}$ and re-run Dijkstra for the remaining size.
• Failover → if a venue rejects, mark its edges weight $\infty$ and continue; the path automatically reroutes.

---

Beyond Classic Dijkstra

• $k$-shortest paths for order slicing across the top-k cheapest routes.
• Constrained shortest path where time-to-fill $\le T_\text{max}$ becomes an additional dimension.
• Multi-objective optimisation: Pareto-efficient frontiers via ε-constraint or genetic algorithms when cost and information leakage are both critical.

---

Complexity Check

With quantity discretised to lots of $\Delta Q$:

• $V = Q / \Delta Q + 1$
• $E = O(V \cdot N)$

Thus

which is tractable as long as $\Delta Q$ isn’t too fine.

---

Takeaways

• Model each venue as an edge whose weight equals all-in cost per fill.
• Run Dijkstra to discover the cheapest execution path from full size to zero.
• Update incrementally on quote changes, no full recompute needed.
• Extend with $k$-shortest, latency constraints, or multi-objective scoring for production-grade SORs.

By borrowing a 1950s graph algorithm, we can tame a 2020s marketplace, transforming fragmented liquidity into a coherent, mathematically optimal path. Happy routing 🚀

---

Disclaimer: This article is educational and not trading advice. Live deployment requires rigorous back-testing, venue-specific rules, and risk controls.