How to get the shortest path in the Flightroutes table

Question

I have problems getting an application to get all stops on a flight.

I have a table with flights, as shown below, where there is a source-airport and destination airport. Now I want to get the shortest flights (smallest stops) from Airport A to Airport B, there is no direct route from A to B, so I need to connect several routes together.

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

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

but not

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

Here are some test data

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

My attempt 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 the routes that start at Source-Airport 18. And if I try differently, I get a loop problem.

Hope you guys can help me. Thank you very much in advance!

Answer 1

Use connect by nocycle and the rank() function:

 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 

Answer 2

Here is one way to recursively construct a path. Use the CYCLE clause to avoid loop exceptions. You get the shortest path from found paths using 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; 

Besides KEEP FIRST this is standard SQL. Instead, you can use the SELECT path FROM cte WHERE dst_apid = 1403 FETCH FIRST 1 ROW ONLY to make this standard compatible. Oracle supports this syntax since 12c.

Answer 3

If you need a line per flight, the only solution that comes to mind is two recursive queries. The first builds flight routes with numbers 1, 1.1, 1.2, 1.1.1, etc .; seconds collect flights belonging to the same route. Pretty hard:

 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; 

Use ROW_NUMBER instead of RANK if you don't need links.