How to Get the Shorthest Path in a Flightroutes-Table

Question

I have trouble in getting a statement to get all stopovers on a flight.

I have table with flightroutes as below, which has a source-airport and a destination-airport. Now i want to get the shortest flightroutes (the least stopovers) from Airport A to Airport B, there is no direct route from A to B so i have to connect several routes together.

So for example, if i want to go from 18 to 1403 i want to get the routes

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

and not

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

Here is some test data

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

My try looks like this:

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;

But this way i only get all routes which start at source-airport 18. And if i try another way, i get a loop-problem.

Hope you guys can help me. Many thanks in advance!

Answer 1

Here is one way to build the path recursively. Use the CYCLE clause to avoid cycle exceptions. You get the shortest path from the found paths with Oracle's 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;

Apart from KEEP FIRST this is standard SQL. You could use SELECT path FROM cte WHERE dst_apid = 1403 FETCH FIRST 1 ROW ONLY instead to make this standard compliant. Oracle supports this syntax as of 12c.

Answer 2

Use connect by nocycle and function 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

Demo:

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