如何计算源和目标之间的跳数？

Question

我在 table 源和目标中有两列，如下所示。

source delivery
  s1      d1
  d1      d2
  d2      f1
  s2      d3
  d3      d4
  d4      d5
  d5      f2

  source - s1 destination f1
  source - s2 destination f2

如何获取源和目标之间的停靠点数？例如：源 s1 -> 目标 f1 在它们之间有 3 个停靠站源 s2 -> 目标 f2 之间有 4 个站点

我熟悉 SQL 查询，但从未写过或遇到过这样的问题。谁能告诉我如何为上述问题编写 sql 查询？即使有另一个问题也有同样的问题，link/question 可以帮助我理解如何写它。

Answer 1

如果你是运行 MySQL 8.0，你可以用递归查询来实现：

with recursive cte as (
    select source, delivery, 1 hops 
    from mytable t
    where not exists (select 1 from mytable t1 where t1.delivery = t.source)
    union all 
    select c.source, t.delivery, c.hops + 1
    from cte c
    inner join mytable t on t.source = c.delivery
)
select source, delivery, hops
from cte c
where hops = (select max(c1.hops) from cte c1 where c1.source = c.source)

递归查询的锚点是没有传入的节点link；然后，它遍历每条路径，同时跟踪原始节点和跳数。最后，外部查询过滤每个路径的最后一个节点。

Demo on DB Fiddle:

source | delivery | hops
:----- | :------- | ---:
s1     | f1       |    3
s2     | f2       |    4

如何计算源和目标之间的跳数？

How to calculate number of hops between sourcee and destination?

mysql

sql

recursive-query

hierarchical-query