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 &quot;depth_limit&quot; 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 &lt; 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 &lt;&gt; 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 &quot;conversion paths&quot; 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'.