How do I find all shortest path (distance) between the source and all the possible destinations in a SQL Statement?

The Oracle (tm) Users' Co-Operative FAQ

How do I find all shortest path between the source and all the possible destinations in a SQL Statement?

Back to index of questions

The following SQL query pattern can be used to find all shortest path (distance) between the source and all the possible destinations in a SQL Statement.

create table IOT

(

    source        varchar2(10),

    destination   varchar2(10),

    distance      number,

    PRIMARY KEY (source, destination )

) ORGANIZATION INDEX  compress 1;

insert into IOT values ( 'A', 'Z', 3 );

insert into IOT values ( 'A', 'B', 3 );

insert into IOT values ( 'B', 'C', 3 );

insert into IOT values ( 'C', 'Z', 3 );

insert into IOT values ( 'A', 'F', 3 );

insert into IOT values ( 'A', 'W', 1 );

insert into IOT values ( 'W', 'Z', 1 );

SQL> select * from IOT;

SOURCE     DESTINATIO   DISTANCE                                               

----------         ----------             ----------                                                

A                  B                        3                                               

A                  F                        3                                               

A                  W                       1                                                

A                  Z                        3                                               

B                  C                        3                                               

C                  Z                        3                                               

W                 Z                        1  

SQL> variable src varchar2(28)

SQL> exec :src := 'A'

PL/SQL procedure successfully completed.

SELECT src, dest, path , min_dist

FROM

 (SELECT src,  dest, path, sum_dist,

       MIN(sum_dist) OVER (PARTITION BY src, dest) min_dist

 FROM

  (SELECT DISTINCT source src, destination dest, path,

        sum(to_number( SUBSTR(x,

                       INSTR (x, ',', 1, LEVEL  ) + 1,

                       INSTR (x, ',', 1, LEVEL+1) -

      INSTR (x, ',', 1, LEVEL) -1 ))) OVER (PARTITION BY path) sum_dist

  FROM

 (

   SELECT  connect_by_root source as source,  destination,

           sys_connect_by_path(distance, ',')||',' x,

           :src|| sys_connect_by_path(destination, ',') path        

   FROM  IOT

   START WITH source  = :src

   CONNECT by NOCYCLE PRIOR destination = source

   AND source != :src

  )

  CONNECT BY PRIOR path = path

  AND INSTR (x, ',', 1, LEVEL+1) > 0

  AND PRIOR dbms_random.string ('p', 10) IS NOT NULL

  )

 )

 WHERE sum_dist = min_dist

 ORDER BY min_dist

SRC DEST  PATH     MIN_DIST_NODE                                                          

--- ----  ------   -------------                                                      

A   W     A,W       1                                                         

A   Z     A,W,Z     2                                                                 

A   B     A,B       3                                                               

A   F     A,F       3                                                   

A   C     A,B,C     6                                                                     

SQL> spool off

Back to top

Back to index of questions