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.

Thinking about this out loud, we should always begin with:
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'.

StackExchange Database Administrators Q#291751, answer score: 9