Как рассчитать количество прыжков между источником и местом назначения? - PullRequest
Новая
       36

Как рассчитать количество прыжков между источником и местом назначения?

1 голос
/ 19 марта 2020

У меня есть два столбца в таблице источника и места назначения, как показано ниже. 

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 запрос для вышеупомянутой проблемы? Даже если есть другой вопрос с той же проблемой, эта ссылка / вопрос может мне очень помочь в понимании того, как его написать.

1 Ответ

2 голосов
/ 19 марта 2020

Если вы используете 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)

Якорь рекурсивного запроса - это узлы, которые не имеют входящей ссылки; затем он проходит по каждому пути, сохраняя при этом исходные узлы и количество прыжков. Наконец, внешние запросы фильтруются на последнем узле для каждого пути.

Демонстрация на DB Fiddle : 

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