mysqlsqlrecursive-queryhierarchical-query

How to calculate number of hops between sourcee and destination?


I have two columns in a table source and destination as below.

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

  source - s1 destination f1
  source - s2 destination f2

How do I get the count of number of stops between source and destination ? For ex: source s1 -> destination f1 has 3 stops between them and source s2 -> destination f2 has 4 stops between them

I am familiar with SQL queries but never had written or encountered a problem like this. Could anyone let me know how can I write a sql query for the aforementioned problem ? Even if there is another question with the same problem, that link/question could help me a lot in understanding how to write it.


Solution

  • If you are running MySQL 8.0, you can do this with a recursive query:

    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)
    

    The anchor of the recursive query is nodes that have no incoming link; then, it walks each path, while keeping track of the original nodes and of the count of hops. Finally, the outer query filters on the last node per path.

    Demo on DB Fiddle:

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