再帰with句08 最小全域木問題

SQLパズル

最小全域木を求める。

問題


答え

データ作成スクリプト

create table minTree(
ID     char(3),
nextID char(3),
cost   integer);

insert into minTree values
('A','B',5),
('A','C',2),
('B','C',4),
('B','D',2),
('C','D',3),
('C','E',2),
('D','E',6),
('D','F',6),
('E','F',4);

insert into minTree
select nextID,ID,cost from minTree;
commit;

SQL

with X(Level,ID,nextID,cost,path) as(
select 1,ID,nextID,cost,cast(ID || nextID as varchar(400))
  from minTree
 where ID = 'A'
union all
select X.Level+1,b.ID,b.nextID,
case when LOCATE(b.ID || b.nextID,X.path) = 0
      and LOCATE(b.nextID || b.ID,X.path) = 0
     then X.cost+b.cost
     else X.cost end,
X.path || ',' || b.ID || b.nextID
  from X,minTree b
 where X.nextID = b.ID
   and X.cost < 5+2+4+2+3+2+6+6+4
   and X.Level <= 10)
select cost,path
  from (select cost,path,
        rank() over(order by cost,Length(path)) as rn
          from X
         where LOCATE('A',path) != 0
           and LOCATE('B',path) != 0
           and LOCATE('C',path) != 0
           and LOCATE('D',path) != 0
           and LOCATE('E',path) != 0
           and LOCATE('F',path) != 0) d
 where rn = 1;

解説

Javaアルゴリズムパズル 3-10 最小全域木問題

---