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;