如何获得Flightroutes表中最短的路径

Question

我无法获得一份声明,以便在航班上获得所有中途停留.

我有下面的flightroutes表,它有一个源机场和一个目的地机场.现在我想从机场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

用途connect by nocycle及作用rank()：

select path
  from (
    select r.*, rank() over (order by lvl) rnk
      from (select routes.*, level lvl, 
                   sys_connect_by_path(src_apid, '->')||'->'||dst_apid path
              from routes 
              connect by nocycle src_apid = prior dst_apid and src_apid <> 1403
              start with src_apid = 18) r
      where dst_apid = 1403 )
  where rnk = 1

演示：

with routes (src_apid, dst_apid ) as (
    select 18,   24 from dual union all
    select 24,   87 from dual union all
    select 87,   99 from dual union all
    select 87, 1403 from dual union all
    select 99,   18 from dual union all
    select 99, 1403 from dual )
select path
  from (
    select r.*, rank() over (order by lvl) rnk
      from (select routes.*, level lvl, 
                   sys_connect_by_path(src_apid, '->')||'->'||dst_apid path
              from routes 
              connect by nocycle src_apid = prior dst_apid and src_apid <> 1403
              start with src_apid = 18) r
      where dst_apid = 1403 )
  where rnk = 1

PATH
--------------------
->18->24->87->1403