Floyd-Warshall All-Pairs Shortest Paths

The Floyd-Warshall algorithm computes the shortest distance between every pair of nodes in a weighted graph, for example, the cheapest currency-conversion path between every pair of currencies in an FX network, including indirect routes through intermediate currencies. Instead of running a single-source shortest-path search separately from each starting node, it fills in one distance matrix for all pairs at once.

The core idea is a triple loop: for every possible intermediate node $k$, and every pair of nodes $(i, j)$, check whether routing from $i$ to $j$ through $k$ is shorter than the best known direct route, that is, update $d_{ij} \leftarrow \min(d_{ij}, d_{ik} + d_{kj})$. Doing this for every $k$ from 1 to $n$, in order, guarantees that by the end, every pair's distance has considered every possible intermediate node as a potential shortcut. For a graph with $n$ currencies, this costs $O(n^3)$ time, for $n = 20$ currencies, about $20^3 = 8{,}000$ update checks, comfortably fast even on modest hardware.

Concretely, if converting USD to EUR directly implies a rate corresponding to a "distance" of 5 (in log-rate terms, so distances add along a path), but USD to JPY to EUR sums to a distance of 4.2, the algorithm updates the USD-EUR entry to reflect the cheaper indirect route the moment JPY is considered as intermediate node $k$, this is exactly the check underlying cross-currency triangular-arbitrage detection.