如何获取Flightroutes中的最短路径 - 表

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

使用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 

Answer 2

这里是递归构建路径的一种方式。使用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起支持此语法。

Answer 3

如果您想要每个航班都有一排，唯一想到的解决方案就是两个递归查询。第一个建立编号为1,1.1,1.2,1.1.1等的航线;秒收集属于同一路线的航班。相当复杂：

with cte1 (routepart, pos, src_apid, dst_apid) as 
(
    select to_char(rownum) as routepart, 1 as pos, src_apid, dst_apid 
    from routes 
    where src_apid = 18 
    union all 
    select cte1.routepart || '-' || rownum, pos + 1, r.src_apid, r.dst_apid 
    from cte1 
    join routes r on r.src_apid = cte1.dst_apid 
    where cte1.dst_apid <> 1403 
) 
cycle src_apid set cycle to 1 default 0 
, cte2 (route, routepart, pos, src_apid, dst_apid) as 
(
    select routepart as route, routepart, pos, src_apid, dst_apid 
    from cte1 
    where dst_apid = 1403 
    union all 
    select cte2.route, cte1.routepart, cte1.pos, cte1.src_apid, cte1.dst_apid 
    from cte1 
    join cte2 on cte2.routepart like cte1.routepart || '%' 
      and nvl(length(regexp_replace(cte2.routepart, '[[:digit:]]', '')), 0) = 
       nvl(length(regexp_replace(cte1.routepart, '[[:digit:]]', '')), 0) + 1 
) 
cycle src_apid set cycle to 1 default 0 
select pos, src_apid, dst_apid 
from 
(
    select 
    cte2.*, 
    rank() over (order by length(regexp_replace(route, '[[:digit:]]', ''))) as rn 
    from cte2 
) 
where rn = 1 
order by route, pos; 

使用ROW_NUMBER，而不是RANK如果你不想联系。