トップページに戻る    次のSQLパズルへ    前のSQLパズルへ

10-139 最短距離問題

SQLパズル

travelテーブル
origin        destination   distance
------------  ------------  --------
バリー        トロント            90
トロント      バリー              90
キッチナー    トロント           105
トロント      キッチナー         105
バリー        ハンツビル         125
ハンツビル    バリー             125
ハンツビル    ノースベイ         130
ノースベイ    ハンツビル         130
ペンブローク  オタワ             150
オタワ        ペンブローク       150
キッチナー    バリー             155
バリー        キッチナー         155
トロント      ベルビル           190
ベルビル      トロント           190
ノースベイ    ペンブローク       220
ペンブローク  ノースベイ         220
ベルビル      オタワ             230
オタワ        ベルビル           230
ベルビル      ペンブローク       230
ペンブローク  ベルビル           230
ハンツビル    ペンブローク       245
ペンブローク  ハンツビル         245

キッチナーからペンブロークまでの経路のリストと、距離の合計を、
全て列挙する



出力結果
距離  ルート
----  -------------------------------------------------------------
 525  キッチナー,トロント,ベルビル,ペンブローク
 525  キッチナー,バリー,ハンツビル,ペンブローク
 565  キッチナー,トロント,バリー,ハンツビル,ペンブローク
 630  キッチナー,バリー,ハンツビル,ノースベイ,ペンブローク
 665  キッチナー,バリー,トロント,ベルビル,ペンブローク
 670  キッチナー,トロント,バリー,ハンツビル,ノースベイ,ペンブローク
 675  キッチナー,トロント,ベルビル,オタワ,ペンブローク
 815  キッチナー,バリー,トロント,ベルビル,オタワ,ペンブローク


データ作成スクリプト

create table travel(
origin      varchar2(12),
destination varchar2(12),
distance    number(3),
primary key(origin, destination));

insert into travel
      select 'キッチナー'  ,'トロント',    105 from dual
union select 'キッチナー'  ,'バリー',      155 from dual
union select 'ノースベイ'  ,'ペンブローク',220 from dual
union select 'ペンブローク','オタワ',      150 from dual
union select 'バリー'      ,'トロント',     90 from dual
union select 'トロント'    ,'ベルビル',    190 from dual
union select 'ベルビル'    ,'オタワ',      230 from dual
union select 'ベルビル'    ,'ペンブローク',230 from dual
union select 'バリー'      ,'ハンツビル',  125 from dual
union select 'ハンツビル'  ,'ノースベイ',  130 from dual
union select 'ハンツビル'  ,'ペンブローク',245 from dual;

insert into travel
select destination, origin, distance
from travel;
commit;


SQL

col ルート for a70

select distinct
(select sum(b.distance) from travel b
  where instr(RegExp_Replace(a.RowIDList,'^(.+),.+$','\1'),RowIDToChar(b.RowID)) > 0) as 距離,
substr(ルート,2) as ルート
  from (select sys_connect_by_path(RowIDToChar(RowID),',') as RowIDList,
        sys_connect_by_path(origin,',') as ルート
         from travel
        where connect_by_isleaf=1
          and origin = 'ペンブローク'
        Start With origin = 'キッチナー'
       connect by nocycle prior destination = origin
           and prior origin != 'ペンブローク') a
where not RegExp_Like(ルート,'(,[^,]+).*\1')
order by 距離;


解説

経路のRowIDを控えておいて、
sumで合計を求めてます