sql - 如何在飞行路线表中获得最短路径

Question

我很难获得一份声明，以获取航类的所有中途停留时间。

我的航线表如下，其中有一个源机场和一个目的地机场。
现在我想获得从机场 A 到机场 B 的最短航线(最少中途停留)，没有从 A 到 B 的直达路线，所以我必须将多条路线连接在一起。

例如，如果我想从 18 到 1403，我想获取路线

(18 > 24 | 24 > 87 | 87 > 1403) 

并不是

(18 > 24 | 24 > 87 | 87 > 99| 99 > 1403)

这是一些测试数据

src_apid | dst_apid
---------+----------
18       | 24
24       | 87
87       | 99
87       | 1403
99       | 18
99       | 1403

我的尝试看起来像这样:

WITH rejkabrest (
src_apid,
dst_apid
) AS (
SELECT
    src_apid,
    dst_apid
FROM
    routes
WHERE
    src_apid = 18  
UNION ALL 
SELECT
    a.src_apid,
    a.dst_apid
FROM
    routes a
    INNER JOIN rejkabrest b ON a.src_apid = b.dst_apid
    WHERE b.dst_apid = 1403
) SELECT
src_apid, dst_apid
FROM
rejkabrest;

但是这样我只能得到从源机场 18 开始的所有路线。如果我尝试另一种方式，我会遇到循环问题。

希望你们能帮帮我。提前谢谢了!

Answer 1

这是递归构建路径的一种方法。使用 CYCLE子句以避免循环异常。您可以使用 Oracle 的 KEEP FIRST 从找到的路径中获得最短路径。 .

with cte (dst_apid, path, stops) as
(
  select dst_apid, src_apid || ' > ' || dst_apid as path, 0 as stops
  from routes
  where src_apid = 18  
  union all 
  select r.dst_apid, cte.path || ' > ' || r.dst_apid, cte.stops + 1
  from cte 
  join routes r on r.src_apid = cte.dst_apid
  where cte.dst_apid <> 1403
)
cycle dst_apid set cycle to 1 default 0
select max(path) keep (dense_rank first order by stops)
from cte
where cte.dst_apid = 1403;

除了 KEEP FIRST这是标准的 SQL。您可以使用 SELECT path FROM cte WHERE dst_apid = 1403 FETCH FIRST 1 ROW ONLY而是使该标准符合标准。 Oracle 从 12c 开始支持此语法。