MySQL 两个节点之间的最短路径

Question

我有一个 MySQL 表，定义如下:

从路径中选择*

source | destination
1 | 2
1 | 3
2 | 4
4 | 5
3 | 5

我试图找到 1 和 5 之间的最短路径，但不确定哪个 SQL 查询会得到该结果。这是我现在拥有的:

WITH RECURSIVE cte AS
(
  SELECT destination, CAST(destination AS CHAR(200)) AS path
  FROM paths WHERE source = 1
  UNION ALL
  SELECT c.destination, CONCAT(cte.path, ",", c.destination)
  FROM paths c JOIN cte ON cte.destination=c.source
)
SELECT * FROM cte ORDER BY path;

我不确定如何将上面的查询限制为仅查找以 5 结尾的路径。我正在寻找的示例:

1 到 5 之间的所有路径:

• (1 -> 2)、(2 -> 4)、(4 -> 5)
• (1 -> 3)，(3 -> 5)

在这种情况下，我希望查询返回的最短路径是第二个选项。

Answer 1

你离我们并不远。只需在递归中添加路径的长度即可。然后过滤目标节点的最终结果，并使用 ORDER BY 路径长度和 LIMIT 只得到一条最短路径(如果有多个路径具有最小值)其中之一的长度是随机选择的)。

WITH RECURSIVE
cte
AS
(
SELECT p.destination,
       concat(p.source, '->', p.destination) path,
       1 length
       FROM paths p
       WHERE p.source = 1
UNION ALL
SELECT p.destination,
       concat(c.path, '->', p.destination) path,
       c.length + 1 length
       FROM cte c
            INNER JOIN paths p
                       ON p.source = c.destination
       WHERE c.destination <> 5
)
SELECT c.path
       FROM cte c
       WHERE c.destination = 5
       ORDER BY c.length
       LIMIT 1;

db<>fiddle

如果图中可以存在循环，您可能会考虑的一件事是循环处理。除非节点 5 处于这样的循环中，否则您将陷入无限递归。