The Oracle (tm) Users' Co-Operative FAQ

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


Author's name: Frank Zhou

Author's Email:zhou328@comcast.net

Date written: 18th December 2006

Oracle version(s): 10.2

How do I find the shortest path (distance) between the source and the 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 INDEXcompress 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 )

†† SELECTconnect_by_root source as source,destination,

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

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

†† FROMIOT

†† WHEREdestination = :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

 

 

SRCDEST††† PATH††††††††† SHORTEST_DIST††††††††††††††††††††††††††††††††††††††††††††††††

---- -----†† ------------- -------------†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

A††† Z†††††† A,W,Z†††††††2††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

SQL> exec :remove_Path := 'W'

 

PL/SQL procedure successfully completed.

 

SQL> /

 

SRCDEST††† PATH††††††††† SHORTEST_DIST††††††††††††††††††††††††††††††††††††††††††††††††

---- -----†† ------------- -------------†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††††††††††††††††

A††† Z†††††† A,Z†††††††††† 3†††††††††††††††††††††††††††††††††††††††††††††††††

††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††

 

SQL> spool off;


 

Back to top

Back to index of questions