トップページに戻る
次の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;
解説