2018-10-23

Finding shortest paths in lenght from a hierarchy

A slight modification to my previous post. This way it is possible to find shortest paths from all start nodes in a graph to a specified end point.
with tre as (
select 0 parent, 1 child, 1 len from dual union all
select 1 parent, 2 child, 2 len from dual union all
select 2 parent, 3 child, 3 len from dual union all
select 3 parent, 1 child, 4 len from dual union all
select 3 parent, 4 child, 5 len from dual union all
select 4 parent, 5 child, 6 len from dual union all
select 5 parent, 6 child, 7 len from dual union all
select 2 parent, 5 child, 20 len from dual
), rcte( root, parent, child, len, lvl, foundpth, pthlen, minpthlen, pth) as (
select t.parent
     , t.parent
     , t.child
     , t.len
     , 1 lvl
     , case when t.child = :endnode then 1 else 0 end foundpth
     , t.len pthlen
     , case when t.child = :endnode then t.len else 9999999 end minpthlen
     , t.parent||'-'||t.child pth
  from tre t
 where t.parent != :endnode
union all
select r.root
     , t.parent
     , t.child
     , t.len
     , r.lvl+1 lvl
     , case when t.child = :endnode then 1 else 0 end
     , r.pthlen+t.len pthlen
     , min(case when t.child = :endnode then r.pthlen+t.len else 9999999 end)over(partition by r.root) minpthlen
     , r.pth||'-'||t.child pth
  from tre t, rcte r
 where t.parent = r.child 
   and r.pthlen + t.len < r.minpthlen 
  ) search breadth first by parent,child set ordr
    cycle parent,child set cycle to 1 default 0
, pths as (
select root,child,lvl,pthlen,pth,cycle,foundpth,row_number()over(partition by root order by pthlen, lvl, pth) rn
  from rcte
 where foundpth = 1
)
select * 
  from pths 
 where rn=1
 order by root,pthlen, lvl, pth 
;

No comments:

Post a Comment

About Me

My photo
I am Timo Raitalaakso. I have been working since 2001 at Solita Oy as a Senior Database Specialist. My main focus is on projects involving Oracle database. Oracle ACE alumni 2012-2018. In this Rafu on db blog I write some interesting issues that evolves from my interaction with databases. Mainly Oracle.