Jak uzyskać najkrótszą ścieżkę w Flightroutes-Table

Question

Mam problem z uzyskaniem oświadczenia, aby uzyskać wszystkie międzylądowania na lot.

Mam stół z lotkami jak poniżej, który ma lotnisko-źródło i lotnisko docelowe. Teraz chcę uzyskać najkrótsze loty (najmniejsze międzylądowania) z lotniska A na lotnisko B, nie ma bezpośredniej trasy od A do B, więc muszę połączyć kilka tras razem.

Tak na przykład, jeśli chcę, aby przejść od 18 do 1403 chcę uzyskać trasy

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

i nie

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

Oto dane testowe

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

Moja próba wygląda następująco:

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; 

Ale w ten sposób otrzymuję tylko wszystkie trasy, które rozpoczynają się od źródła-port lotniczy 18. A jeśli spróbuję inaczej, dostaję problem z pętlą.

Mam nadzieję, że możesz mi pomóc. Z góry bardzo dziękuję!

Answer 1

Zastosowanie connect by nocycle i funkcja 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 

Answer 2

Oto jeden sposób, aby zbudować drogę rekurencyjnie. Użyj klauzuli CYCLE, aby uniknąć wyjątków cyklu. Najkrótsza ścieżka od znalezionych ścieżek otrzymasz z 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; 

Jest to standardowy kod SQL, poza KEEP FIRST. Zamiast tego możesz użyć SELECT path FROM cte WHERE dst_apid = 1403 FETCH FIRST 1 ROW ONLY, aby uzyskać zgodność z tym standardem. Oracle obsługuje tę składnię od 12c.

Answer 3

Jeśli potrzebujesz wiersza na lot, jedynym rozwiązaniem, które przychodzi Ci na myśl, są dwa zapytania cykliczne. Pierwszy buduje trasy lotu z numerami 1, 1.1, 1.2, 1.1.1 itd .; sekundy zbierają loty należące do tej samej trasy. Dość skomplikowane:

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; 

Zastosowanie ROW_NUMBER zamiast RANK jeśli nie chcesz więzi.