mysql - 如何在MYSQL中编写类似 "shortest path"的命令或至少 "find a path"命令？

Question

想象一下，表格中有社交媒体数据，如下所示:

u1 u2
0  3
1  2
1  4
2  3
3  1
3  4

这意味着:

• 用户 0 关注用户 3
• 用户 1 关注用户 2
• 用户 1 关注用户 4
• ...

现在我想知道:是否有从用户 0 到用户 2 的方式/路径？

是的。用户 0 关注用户 3。用户 3 关注用户 1。用户 1 关注用户 2。

但是如何通过 SQL 命令解决这个问题呢？

我想知道是否有这样的路径。可选我想知道路径是什么。是否有可能以某种方式获得最短路径？

Answer 1

下面的查询适用于 MySQL 8.x，因为它需要“递归公用表表达式”(递归 CTE):

with n (initial, path, current) as (
  select u1, concat('', u1, '/', u2), u2  from my_table 
    where u1 = 0 -- initial node
  union all 
  select n.initial, concat(n.path, '/', m.u2), m.u2
    from my_table m
    join n on n.current = m.u1
)
select * from n 
  where current = 2 -- target node

但是，如果您使用的是 MySQL 5.x，那么您就不走运了(据我所知)。