4-13 経路を取得

SQLパズル

航空便表テーブル
出発地        目的地             費用
------------  ------------      ----
パリ          ニューヨーク         6
パリ          デンバー             9
パリ          ダラス               8
ニューヨーク  シカゴ               2
シカゴ        サンフランシスコ     4
デンバー      サンフランシスコ     4
ダラス        ニューヨーク         3
ダラス        サンフランシスコ     6

パリからサンフランシスコまでの経路リストと、合計費用を取得する

出力結果
経路                                              合計費用  乗継回数
-----------------------------------------------  --------  --------
パリ,ニューヨーク,シカゴ,サンフランシスコ                12         2
パリ,デンバー,サンフランシスコ                           13         1
パリ,ダラス,サンフランシスコ                             14         1
パリ,ダラス,ニューヨーク,シカゴ,サンフランシスコ          17         3

データ作成スクリプト

create table 航空便表(
出発地 text,
目的地 text,
費用   integer);

insert into 航空便表 values('パリ'        ,'ニューヨーク'    ,6),
                           ('パリ'        ,'デンバー'        ,9),
                           ('パリ'        ,'ダラス'          ,8),
                           ('ニューヨーク','シカゴ'          ,2),
                           ('シカゴ'      ,'サンフランシスコ',4),
                           ('デンバー'    ,'サンフランシスコ',4),
                           ('ダラス'      ,'ニューヨーク'    ,3),
                           ('ダラス'      ,'サンフランシスコ',6);

SQL

with recursive rec(出発地,目的地,費用,path,LV) as(
select 出発地,目的地,費用,出発地 || ',' || 目的地,0
  from 航空便表
 where 出発地 = 'パリ'
union all
select b.出発地,b.目的地,a.費用+b.費用,a.path || ',' || b.目的地,a.LV+1
  from rec a,航空便表 b
 where a.目的地=b.出発地
   and a.目的地 != 'サンフランシスコ')
select path,費用 as 合計費用,LV as 乗継回数 from rec
 where 目的地 = 'サンフランシスコ'
order by 費用;

解説

最短距離問題の基本的な問題といえるでしょう。

---