SQL Server查询以查找从城市A到城市B的所有路由以及传输

Question

在面试开发人员职位时,我被问到这个问题.

任务:在SQL Server表写入查询中存储飞行路线,该查询将查找从城市A到城市B的所有路线,无需转移,只需一次或两次转移.例如,你有路线:

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

您需要找到所有从洛杉矶到伦敦的接送路线.结果应该是这样的

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

我的解决方案是这样

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'

工作,但看起来不是很好,如果我们需要找到3,4,5或更多转移的路线,我们需要添加更复杂选择的新联合.

对于这个特殊的例子,它很好,因为人们通常对超过2次转移的航班不感兴趣.但总的来说,我认为这个查询看起来更好.也许有人可以使用更一般的查询来解决此任务.谢谢.

Answer 1

是的,您为所有RDB提供了通用的SQL解决方案.我看到你有一个提示 - SQL Server.它支持递归CTE,可用于解决此任务.

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

所以,这里有SQL Server的通用解决方案,你可以通过传输计数来过滤它们.