时间戳

首页 > 解决方案 > MySQL 两个节点之间的最短路径

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

问题描述

我有一个如下定义的 MySQL 表：

SELECT * FROM paths

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之间的所有路径：

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

标签： mysqlsql

解决方案

你不是太远了。只需在递归中添加路径的长度。然后过滤目标节点的最终结果并使用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<>小提琴

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

推荐阅读