# How can I find the shortest path between two currencies?

I have table `currency_pair(c1, c2)`; values are `(usd,bnb), (cake,bnb), (cake,eth)`.

I need to find the shortest path that allows me to compare `usd` to `eth`.

The result here would be those same values. I can then use the first pair to establish a usd-bnb relationship, which I can then use to calculate a usd-cake relationship, which I can then use to compute usd-eth.

Since order is not determinate, the first step I did was create a materialized view, `currency_pair_map(c1, c2)`, which is a union of `select c1, c2 union select c2, c1`. This would seem to simplify the logic.

If I am thinking about this correctly, what I need to do is use WITH RECURSIVE? I should also have some sort "depth_limit" parameter that ensures that a query fails if it is impossible to establish a pair.

``````SELECT *
FROM currency_pair
WHERE
c1 = 'usd' AND
c2 = 'eth'
``````

If there is a result, we should end there.

If there is not, then we need to find all `usd-*` pairs and continue search until we find one that ends with `eth`.

Using this logic, so far I have:

``````
WITH RECURSIVE pair_route AS (
SELECT
1 depth,
cp1.id,
cp1.c1,
cp1.c2
FROM currency_pair cp1
WHERE
cp1.c1 = 'usd'
UNION
SELECT
pr1.depth + 1,
cp2.id,
cp2.c1,
cp2.c2
FROM pair_route pr1
INNER JOIN currency_pair cp2 ON cp2.c1 = pr1.c2
WHERE
pr1.depth < 4
)
SELECT *
FROM pair_route;
``````

I think this is correct. Now I just need to track path (IDs) and identify the shortest paths.

You could use this recursive query:

``````WITH RECURSIVE c AS (
SELECT c1, c2 FROM currency_pair
UNION
SELECT c2, c1 FROM currency_pair
), curr_path AS (
SELECT ARRAY[c1, c2] AS path
FROM c
WHERE c2 = 'usd'
UNION ALL
SELECT c.c1 || p.path
FROM c
JOIN curr_path AS p
ON c.c2 = (p.path)[1]
WHERE c.c1 <> ALL (p.path)
)
SELECT path
FROM curr_path
WHERE path[1] = 'eth'
ORDER BY cardinality(path)
LIMIT 1;
``````

First, I calculate the symmetric closure.

Then I construct arrays of "conversion paths" by starting with the pairs we have, then prepending new currencies to arrays that can be converted to the first array element and do not yet appear in the array.

Once I have got all conversion chains that end up in `'usd'`, I pick the shortest chain that starts with `'eth'`.

• Perfect. Thank you. May 18, 2021 at 2:57

While Laurenz answer is great, it is not the most efficient.

I found that the best way to do this in production is:

2. then try to find pair by looking up the first leg, the last leg, and all connections
3. then fallback to Laurenz solution

The query mentioned in #2 would look something like this:

``````WITH
pair_symmetric_closure AS (
SELECT
cp1.c1,
cp1.c2
FROM currency_pair cp1
UNION
SELECT
cp1.c2,
cp1.c1
FROM currency_pair cp1
)
SELECT *
FROM pair_symmetric_closure psc1
INNER JOIN pair_symmetric_closure pcp2 ON pcp2.c1 = psc1.c2
INNER JOIN pair_symmetric_closure pcp3 ON pcp3.c1 = pcp2.c2
WHERE
psc1.c1 = 'usd' AND
pcp3.c2 = 'eth';
``````