SQL Server query to find all routes from city A to city B with transfers

Question

I was asked this question while interviewing for developer position.

Task: Having flight routes stored in SQL Server table write query which will find all routes from city A to city B without transfer, with one or two transfers. For instance you have routes:

| From         | To
----------------------
Los Angeles     London   
Los Angeles     New York
New York        London
Los Angeles     Seattle
Seattle         Paris
Paris           London

And you need to find all routes with transfers from Los Angeles to London. The result should be like this

Route
------------------------
Los Angeles->London
Los Angeles->New York->London
Los Angeles->Seattle->Paris->London

My solution was this

select [From] + '->' + [To] as [Route] from Routes where [From] = 'Los Angeles' and [To] = 'London'
union 
select r1.[From] + '->' + r1.[To] + '->' + r2.[To] as [Route] from Routes as r1 
join Routes as r2 on r1.[To] = r2.[From]
where r1.[From] = 'Los Angeles' and r2.[To] = 'London'
union 
select r1.[From] + '->' + r1.[To] + '->' + r2.[To] + '->' + r3.[To] as [Route] from Routes as r1 
join Routes as r2 on r1.[To] = r2.[From]
join Routes as r3 on r2.[To] = r3.[From]
where r1.[From] = 'Los Angeles' and r3.[To] = 'London'

Works but looks not very good and if we need to find routes with 3, 4, 5 or more transfers we need to add new unions with more complex selects.

For this particular example it’s good because the people as a rule are not interested in flights with more than 2 transfers. But in general I think this query can look better. Perhaps someone can solve this task with more general query. Thanks.

Answer 1

Right, you provided working general SQL solution for all RDBs. I see you had here one hint – SQL Server. It supports recursive CTE which can be used to solve this task.

with RoutesCTE as
(
    select CAST([From] + '->' + [To] as nvarchar(max)) as [Route]
          ,0 as TransfersCount
          ,[From]
          ,[To]
    from Routes

    union all

    select r.[Route] + '->' + r1.[To]
          ,TransfersCount + 1
          ,r.[From]
          ,r1.[To]
    from RoutesCTE r
        join Routes r1
            on r.[To] = r1.[From]
                and r1.[To] <> r.[From] 
                  and PATINDEX('%'+r1.[To]+'%', r.[Route]) = 0
)
select [Route]
from RoutesCTE 
where [From] = 'Los Angeles'
    and [To] = 'London'
    and TransfersCount <= 2

So, here you have general solution for SQL Server and you can filter them by transfers count.