如何获取飞行航线中的最短路径-Table

Question

我无法获得声明以获取航班上的所有中途停留。

我有 table 的飞行路线如下，其中有一个源机场和一个目的地机场。现在我想获得从机场 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。

如何获取飞行航线中的最短路径-Table

How to Get the Shorthest Path in a Flightroutes-Table

sql

oracle

shortest-path