2017-04-19 27 views
5

Tüm duraklamaların bir uçuşa girmesi için bir açıklamada sorun yaşıyorum.Bir Uçuş Yolunda En Kısa Yol Nasıl Gidilir?-Tablo

Aşağıdaki gibi bir kaynak-havaalanı ve bir hedef-havaalanı olan uçuş rotaları olan bir tablom var. Şimdi A Havaalanı'ndan B noktasına en kısa uçuş rotalarını (en az durma) almak istiyorum, bu yüzden A'dan B'ye direkt bir yol yok, bu yüzden birkaç rotayı birbirine bağlamalıyım. i 18 ila 1403 gitmek istiyorum

Yani, örneğin, ben burada

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

bazı test verileri

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

değil yolları almak istiyorum

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

Denemem şunun gibi görünüyor:

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; 

Ama bu yolla sadece kaynak-havalimanı 18'den başlayan tüm rotaları alıyorum. Ve eğer başka bir şekilde denersem, bir döngü problemi olur.

Umarım bana yardımcı olabilirsiniz. Şimdiden çok teşekkürler!

+0

https://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm –

+0

[Bu yanıt] (http://stackoverflow.com/a/39119303/5089204) SQL-Server'tır sözdizimi, ancak size yol gösterebilir. Ana hile, ziyaret edilen tüm istasyonlarla büyüyen bir ipi taşımak ve bir yer tekrar ziyaret edildiyse, tekrarlamayı durdurmaktır. – Shnugo

cevap

3

Kullanım connect by nocycle ve fonksiyon 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 
3

İşte yinelemeli yol inşa etmek bir yoludur. Döngü istisnalarını önlemek için CYCLE maddesini kullanın. Oracle'ın KEEP FIRST ile bulunan yollardan en kısa yolu elde edersiniz.

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 dışında bu standart SQL'dir. Bu standardı uyumlu hale getirmek için SELECT path FROM cte WHERE dst_apid = 1403 FETCH FIRST 1 ROW ONLY'u kullanabilirsiniz. Oracle bu sözdizimini 12c'den itibaren desteklemektedir.

+0

Merhaba, cevabınız için teşekkürler. Gelecek okuyucular için 7 numaralı satırda cte.stops'a geçiş yapmayı isteyebilirsiniz (aksi takdirde işe yaramaz, en azından benim için). Tablonun binlerce satırdan beri sorguyu gerçekten gerçekleştiremedim. Performansı artırmak için uçuşlar arasında maksimum durak sayısı eklemek mümkün mü?30 dakika bekledikten sonra hala herhangi bir sonuç alamadım: -/ – Steuerfahndung

+2

Eh, niteleyici olmadan benim için çalışıyor, ama ben açıkça bu Oracle sürümüne bağlı olarak (veya adında bir sütun var) güzergah tablosunda durur). Tabi ki, durma sayısını sınırlayabilirsiniz, örneğin: cte'da cte.dst_apid <> 1403 ve cte.stops <4'. ('cte.stops <4' 4 durağa sınırlar; istediğiniz herhangi bir sayıyı kullanın.) –

1

Uçuş başına bir satır istiyorsanız, akla gelen tek çözüm, iki yinelemeli sorundur. İlk uçuş hatlarını 1, 1.1, 1.2, 1.1.1, vb. saniye, aynı rotaya ait uçuşları toplar. Aksine karmaşık: Eğer bağları istemiyoruz

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; 

Kullanım ROW_NUMBER yerine RANK eğer.

İlgili konular