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

The Oracle (tm) Users' Co-Operative FAQ

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

Back to index of questions

The following SQL query pattern can be used to find the shortest path (distance) between the source and the destination.  (This SQL pattern can also excludes some of the paths from the distance calculation based on the user’s requirement)

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 remove_Path varchar2(28)

SQL> variable src varchar2(28)

SQL> variable dest varchar2(28)

SQL> exec :remove_Path := ''

PL/SQL procedure successfully completed.

SQL> exec :src := 'A'

PL/SQL procedure successfully completed.

SQL> exec :dest := 'Z'

PL/SQL procedure successfully completed.

SELECT source src, destination dest, path, sum_dist shortest_dist

FROM

(SELECT DISTINCT source, destination, 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

 (

   WITH REMOVE_PATH AS (

   SELECT SUBSTR(str,

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

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

           INSTR(str, ',', 1, LEVEL) -1 ) str     

   FROM (SELECT ','||NVL(:Remove_Path, ' ')||','||:src||','||:dest||','

         AS str FROM DUAL)

   CONNECT BY PRIOR STR = STR

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

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

   SELECT  connect_by_root source as source,  destination,

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

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

   FROM  IOT

   WHERE  destination = :dest

   START WITH source  = :src

   CONNECT by nocycle PRIOR destination = source

   AND source NOT IN (SELECT str FROM REMOVE_PATH)

  )

  CONNECT BY PRIOR path = path

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

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

  ORDER BY sum_dist NULLS LAST

)

WHERE ROWNUM = 1

SRC  DEST    PATH          SHORTEST_DIST                                                

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

A    Z       A,W,Z         2                                                                                                    

SQL> exec :remove_Path := 'W'

PL/SQL procedure successfully completed.

SQL> /

SRC  DEST    PATH          SHORTEST_DIST                                                

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

A    Z       A,Z           3                                                 

SQL> spool off;

Back to top

Back to index of questions