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

再帰with句07 最短距離問題

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      char(18),
destination char(18),
distance    integer);

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

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


SQL

with recursive W(origin,destination,distance,path) as(
select origin,destination,0,array[origin::text]
  from travel
 where origin = 'キッチナー'
union all
select b.origin,b.destination,W.distance+b.distance,
W.path || b.origin::text
  from W,travel b
 where b.origin != all(W.path)
   and W.origin != 'ペンブローク'
   and b.destination = W.origin)
select distinct distance,array_to_string(path,',') as path
  from W
 where origin = 'ペンブローク'
order by distance;


解説

OracleSQLパズル 10-139 最短距離問題