如何找到两种货币之间的最短路径？

Question

我有桌子currency_pair(c1, c2)；值是(usd,bnb), (cake,bnb), (cake,eth)。

我需要找到一个让我比较的最短路径usd来eth。

此处的结果将是相同的值。然后我可以使用第一对建立一个 usd-bnb 关系，然后我可以用它来计算 usd-cake 关系，然后我可以用它来计算 usd-eth。

由于顺序是不确定的，我做的第一步是创建一个物化视图，currency_pair_map(c1, c2)，它是 的并集select c1, c2 union select c2, c1。这似乎简化了逻辑。

如果我正确考虑这一点，我需要做的是使用WITH RECURSIVE？我还应该有某种“depth_limit”参数，以确保在无法建立一对时查询失败。

大声思考这个问题，我们应该始终从以下几点开始：

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

如果有结果，我们应该到此为止。

如果没有，那么我们需要找到所有usd-*对并继续搜索，直到找到以 结尾的对eth。

使用这个逻辑，到目前为止我有：

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;

我认为这是正确的。现在我只需要跟踪路径（ID）并确定最短路径。

Answer 1

您可以使用此递归查询：

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;

首先，我计算对称闭包。

然后我从我们拥有的货币对开始构建“转换路径”数组，然后将新货币添加到可以转换为第一个数组元素但尚未出现在数组中的数组。

一旦我获得了所有以 . 结尾的转换链'usd'，我就会选择以'eth'.