Shortest Path Algorithm In Oracle

Connected to Oracle Database 10g Express Edition Release 10.2.0.1.0
Connected as hr

SQL> create table distances(
2 from_city varchar2(16),
3 to_city varchar2(16),
4 distance number
5 );

Table created

SQL> insert into distances values('Istanbul', 'Ankara', 600);

1 row inserted

SQL> insert into distances values('Ankara', 'Izmir', 800);

1 row inserted

SQL> insert into distances values('Istanbul', 'Izmir', 500);

1 row inserted

SQL> insert into distances values('Izmir', 'Antalya', 250);

1 row inserted

SQL> insert into distances values('Ankara', 'Antalya', 450);

1 row inserted

SQL> SELECT * FROM distances;

FROM_CITY TO_CITY DISTANCE
---------------- ---------------- ----------
Istanbul Ankara 600
Ankara Izmir 800
Istanbul Izmir 500
Izmir Antalya 250
Ankara Antalya 450

SQL> SELECT connect_by_root from_city || sys_connect_by_path(to_city, ',') total_path,
2 sys_connect_by_path(distance, '+') total_distance
3 FROM distances
4 START WITH from_city = 'Istanbul'
5 CONNECT BY PRIOR to_city = from_city;

TOTAL_PATH TOTAL_DISTANCE
---------------------------------------- -------------------------------------------------
Istanbul,Ankara +600
Istanbul,Ankara,Izmir +600+800
Istanbul,Ankara,Izmir,Antalya +600+800+250
Istanbul,Ankara,Antalya +600+450
Istanbul,Izmir +500
Istanbul,Izmir,Antalya +500+250

6 rows selected

SQL> --
SQL> DECLARE
2 CURSOR cur_D IS(
3 SELECT tot_path, tot_dis
4 FROM (SELECT sys_connect_by_path(to_city, ',') tot_path,
5 sys_connect_by_path(distance, '+') tot_dis
6 FROM distances
7 START WITH from_city = 'Istanbul'
8 CONNECT BY PRIOR to_city = from_city) t
9 WHERE instr(tot_path,'Antalya') > 0);
10 rec_D cur_D%ROWTYPE;
11 vn_Total NUMBER;
12 vn_MinDistance NUMBER;
13 vs_MinPath VARCHAR2(255);
14 BEGIN
15 vn_MinDistance := 999999999999999999999999999999999999999;
16
17 OPEN cur_D;
18 LOOP
19 FETCH cur_D
20 INTO rec_D;
21 EXIT WHEN cur_D%NOTFOUND;
22 EXECUTE IMMEDIATE 'BEGIN :vn_Total := ' || rec_D.tot_dis || '; END;'
23 USING OUT vn_Total;
24 IF vn_MinDistance > vn_Total THEN
25 vn_MinDistance := vn_Total;
26 vs_MinPath := rec_D.tot_path;
27 END IF;
28
29 dbms_output.put_line(rec_D.tot_path || ' = ' || vn_Total);
30 END LOOP;
31 CLOSE cur_D;
32
33 dbms_output.put_line('Shortest ');
34 dbms_output.put_line(vs_MinPath || ' = ' || vn_MinDistance);
35
36 END;
37 /

,Ankara,Izmir,Antalya = 1650
,Ankara,Antalya = 1050
,Izmir,Antalya = 750
Shortest
,Izmir,Antalya = 750

PL/SQL procedure successfully completed

SQL>