Skip to Main Content

SQL & PL/SQL

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Interested in getting your voice heard by members of the Developer Marketing team at Oracle? Check out this post for AppDev or this post for AI focus group information.

How to use Recursive Subquery Factoring (RSF) to Implement Dijkstra’s shortest path algorithm?

BlaisApr 9 2015 — edited May 4 2015

Can someone who knows Recursive Subquery Factoring (RSF) can tell me if my Dijkstra’s shortest path algorithm is implement correctly and efficiently? Below you will found my SQL query and a trial dataset.

Below my query, a trial dataset and table definition to contain the data:

/*Dijkstra Shortest path*/

WITH UsefulArcs AS

  (SELECT SRC, DST, DISTANCE FROM ARCS

  ),

  Paths (SrcArc, DestArc, SrcPath, DestPath, Path, OpDist, DistPath, DistPathMin) AS

  (SELECT SRC AS SrcArc ,

    DST AS DestArc ,

    SRC AS SrcPath ,

    DST AS DestPath ,

    SRC

    ||'>'

    || DST AS Path ,

    ''

    ||DISTANCE AS OpDist ,

    DISTANCE AS DistPath,

    DISTANCE AS DistPathMin

  FROM UsefulArcs

  WHERE SRC=:prmSource

  UNION ALL

  SELECT a.SRC AS SrcArc,

    a.DST AS DestArc,

    Paths.SrcPath ,

    a.DST AS DestPath ,

    Paths.Path

    ||'>'

    ||a.DST AS Path,

    Paths.OpDist

    ||'+'

    ||a.DISTANCE AS OpDist ,

    Paths.DistPath    +a.DISTANCE                          AS DistPath,

    MIN(Paths.DistPath+a.DISTANCE) OVER (PARTITION BY a.DST) AS DistPathMin

  FROM UsefulArcs a

  INNER JOIN Paths

  ON (Paths.DestArc        =a.SRC)

  WHERE Paths.DistPathMin=Paths.DistPath

  ) SEARCH BREADTH FIRST BY DestPath

  --SEARCH DEPTH FIRST BY DestPath

  SET Order01

SELECT *

FROM Paths

WHERE SrcPath          =:prmSource

AND DestPath           =:prmSink

AND DistPath =

  (SELECT MIN(DistPath) FROM Paths WHERE SrcPath=:prmSource AND DestPath =:prmSink

  )

ORDER BY DistPath;

Set prmSource=1 and prmSink=10.

Dijkstra’s algorithm definition: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


Problems data: http://www.ime.unicamp.br/~andreani/MS515/capitulo7.pdf

CREATE TABLE "ARCS"

   (   "SRC" NUMBER(3,0),

       "DST" NUMBER(3,0),

       "DISTANCE" NUMBER(3,0)

   ) ;

  CREATE TABLE "NODES"

   (   "NODES" NUMBER(3,0)

   ) ;

REM INSERTING into ARCS

SET DEFINE OFF;

Insert into ARCS (SRC,DST,DISTANCE) values ('1','2','2');

Insert into ARCS (SRC,DST,DISTANCE) values ('1','3','4');

Insert into ARCS (SRC,DST,DISTANCE) values ('1','4','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('2','5','7');

Insert into ARCS (SRC,DST,DISTANCE) values ('3','5','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('4','5','4');

Insert into ARCS (SRC,DST,DISTANCE) values ('2','6','4');

Insert into ARCS (SRC,DST,DISTANCE) values ('3','6','2');

Insert into ARCS (SRC,DST,DISTANCE) values ('4','6','1');

Insert into ARCS (SRC,DST,DISTANCE) values ('2','7','6');

Insert into ARCS (SRC,DST,DISTANCE) values ('3','7','4');

Insert into ARCS (SRC,DST,DISTANCE) values ('4','7','5');

Insert into ARCS (SRC,DST,DISTANCE) values ('5','8','1');

Insert into ARCS (SRC,DST,DISTANCE) values ('6','8','6');

Insert into ARCS (SRC,DST,DISTANCE) values ('7','8','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('5','9','4');

Insert into ARCS (SRC,DST,DISTANCE) values ('6','9','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('7','9','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('8','10','3');

Insert into ARCS (SRC,DST,DISTANCE) values ('9','10','4');

REM INSERTING into NODES

SET DEFINE OFF;

Insert into NODES (NODES) values ('1');

Insert into NODES (NODES) values ('2');

Insert into NODES (NODES) values ('3');

Insert into NODES (NODES) values ('4');

Insert into NODES (NODES) values ('5');

Insert into NODES (NODES) values ('6');

Insert into NODES (NODES) values ('7');

Insert into NODES (NODES) values ('8');

Insert into NODES (NODES) values ('9');

Insert into NODES (NODES) values ('10');

  CREATE UNIQUE INDEX "ARCS_PK1" ON "ARCS" ("SRC", "DST")

  ;

  CREATE UNIQUE INDEX "NOEUDS_PK1" ON "NODES" ("NODES")

  ;

  ALTER TABLE "ARCS" MODIFY ("SRC" NOT NULL ENABLE);

  ALTER TABLE "ARCS" MODIFY ("DST" NOT NULL ENABLE);

  ALTER TABLE "ARCS" MODIFY ("DISTANCE" NOT NULL ENABLE);

  ALTER TABLE "ARCS" ADD CONSTRAINT "ARCS_PK" PRIMARY KEY ("SRC", "DST") ENABLE;

  ALTER TABLE "NODES" MODIFY ("NODES" NOT NULL ENABLE);

  ALTER TABLE "NODES" ADD CONSTRAINT "NOEUDS_PK" PRIMARY KEY ("NODES") ENABLE;

  ALTER TABLE "ARCS" ADD CONSTRAINT "ARCS_FK1" FOREIGN KEY ("SRC")

REFERENCES "NODES" ("NODES") ENABLE;

  ALTER TABLE "ARCS" ADD CONSTRAINT "ARCS_FK2" FOREIGN KEY ("DST")

REFERENCES "NODES" ("NODES") ENABLE;

Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on May 18 2015
Added on Apr 9 2015
25 comments
5,715 views