Home » SQL & PL/SQL » SQL & PL/SQL » Find shortest path with visits (PL/SQL)
icon5.gif  Find shortest path with visits [message #589235] Wed, 03 July 2013 10:25 Go to next message
domitek
Messages: 4
Registered: July 2013
Location: Portugal
Junior Member
Hello.

I am find about an algorithm of shortest path with visits certain nodes.

I have a table of Links with this fields: ID_Link, City1, City2 and distance
You have informations about shortest path with visits?

Thanks!
Re: Find shortest path with visits [message #589236 is a reply to message #589235] Wed, 03 July 2013 10:26 Go to previous messageGo to next message
Michel Cadot
Messages: 57645
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Welcome to the forum.

With any SQL or PL/SQL question, please, Post a working Test case: create table (including all constraints) and insert statements along with the result you want with these data then we will be able work with your table and data. Explain with words and sentences the rules that lead to this result.

Before, Please read OraFAQ Forum Guide and How to use [code] tags and make your code easier to read.
Make sure that lines of code do not exceed 80 characters when you format.
Indent the code, use code tags and align the columns in result.
Use the "Preview Message" or "Preview Quick Reply" button to verify.
Also always post your Oracle version, with 4 decimals.

Regards
Michel
Re: Find shortest path with visits [message #589237 is a reply to message #589236] Wed, 03 July 2013 10:31 Go to previous messageGo to next message
BlackSwan
Messages: 21968
Registered: January 2009
Senior Member
Yet another homework assignment using the proverbial Traveling Salesman problem
Re: Find shortest path with visits [message #589240 is a reply to message #589237] Wed, 03 July 2013 10:45 Go to previous messageGo to next message
domitek
Messages: 4
Registered: July 2013
Location: Portugal
Junior Member
CREATE TABLE CITIES
(
  ID_CITY INTEGER PRIMARY KEY,
  DESIGNATION VARCHAR(50)
);
CREATE TABLE LINK
(
  ID_LINK INTEGER PRIMARY KEY,
  CITY_1 INTEGER,
  FOREIGN KEY (CITY_1) REFERENCES CITIES(ID_CITY),
  CITY_2 INTEGER,
  FOREIGN KEY (CITY_2) REFERENCES CITIES(ID_CITY),
  DISTANCE FLOAT,
  DIRECTION CHAR(1)
);

dont is a home work!! it's for an project. I am student of electronic engineer! not informatic!
but TSP don't have a same node initial and finish??
(I don't want that you make me a work but help me a find one solution)

[Updated on: Wed, 03 July 2013 10:46]

Report message to a moderator

Re: Find shortest path with visits [message #589245 is a reply to message #589240] Wed, 03 July 2013 11:47 Go to previous messageGo to next message
Michel Cadot
Messages: 57645
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
INSERT statements and result from data are missing.

Regards
Michel
Re: Find shortest path with visits [message #589296 is a reply to message #589245] Thu, 04 July 2013 02:39 Go to previous messageGo to next message
_jum
Messages: 485
Registered: February 2008
Senior Member
As @BlackSwan mentioned, for basics have a look at Travelling salesman problem.
You could use Oracle Spatial Network Data Model to compute Shortest Path.
icon5.gif  Re: Find shortest path with visits [message #589550 is a reply to message #589296] Mon, 08 July 2013 08:57 Go to previous messageGo to next message
domitek
Messages: 4
Registered: July 2013
Location: Portugal
Junior Member
_jum wrote on Thu, 04 July 2013 08:39
As @BlackSwan mentioned, for basics have a look at Travelling salesman problem.
You could use Oracle Spatial Network Data Model to compute Shortest Path.

For use Oracle Spatial Network Data Model, I have crate a Network in SDO_NET Package?
I have the tables as you can see here http://www.orafaq.com/forum/mv/msg/188464/589240/179253/#msg_589240 and my project is advanced for restructure this part! Don't have a functions on PL/SQL?

Thanks
Re: Find shortest path with visits [message #589562 is a reply to message #589550] Mon, 08 July 2013 10:19 Go to previous messageGo to next message
_jum
Messages: 485
Registered: February 2008
Senior Member
Yes, there are some ways to obtain results in SQL and PL/SQL too, but this depends...
And for a complete test-case the INSERT statements and result from data are missing (see @Michel).

Re: Find shortest path with visits [message #589564 is a reply to message #589562] Mon, 08 July 2013 11:03 Go to previous messageGo to next message
domitek
Messages: 4
Registered: July 2013
Location: Portugal
Junior Member
INSERT INTO CITIES VALUES (1, 'z1');
INSERT INTO CITIES VALUES (2,'z2');
INSERT INTO CITIES VALUES (3,'z3');
INSERT INTO CITIES VALUES (4,'z4');
INSERT INTO CITIES VALUES (5,'z5');
INSERT INTO CITIES VALUES (6,'z6');

INSERT INTO LINK VALUES (1,1,2,120,'N');
INSERT INTO LINK VALUES (2,2,3,120,'3');
INSERT INTO LINK VALUES (3,3,4,120,'N');
INSERT INTO LINK VALUES (4,4,5,120,'N');
INSERT INTO LINK VALUES (5,5,6,120,'N');

you can help-me with the code in pl/sql?

[Updated on: Mon, 08 July 2013 11:07]

Report message to a moderator

Re: Find shortest path with visits [message #589606 is a reply to message #589564] Tue, 09 July 2013 02:48 Go to previous message
_jum
Messages: 485
Registered: February 2008
Senior Member
This is no fitting testcase. There is only one way through the cities ?!
Here is the example from WIKI: Travelling salesman problem and a SQL version with CONNECT BY as a start:
CREATE TABLE CITIES
(
  ID_CITY INTEGER PRIMARY KEY,
  DESIGNATION VARCHAR(50)
);

CREATE TABLE LINK
(
  ID_LINK INTEGER PRIMARY KEY,
  CITY_1 INTEGER,
  FOREIGN KEY (CITY_1) REFERENCES CITIES(ID_CITY),
  CITY_2 INTEGER,
  FOREIGN KEY (CITY_2) REFERENCES CITIES(ID_CITY),
  DISTANCE FLOAT,
  DIRECTION VARCHAR2(2)
);

INSERT INTO CITIES VALUES (1,'A');
INSERT INTO CITIES VALUES (2,'B');
INSERT INTO CITIES VALUES (3,'C');
INSERT INTO CITIES VALUES (4,'D');

INSERT INTO LINK VALUES ( 1,1,2,20,'E');
INSERT INTO LINK VALUES ( 2,1,3,42,'S');
INSERT INTO LINK VALUES ( 3,1,4,35,'SE');
INSERT INTO LINK VALUES ( 4,2,3,30,'SW');
INSERT INTO LINK VALUES ( 5,2,4,34,'S');
INSERT INTO LINK VALUES ( 6,3,4,12,'E');
INSERT INTO LINK VALUES (11,2,1,20,'W');
INSERT INTO LINK VALUES (12,3,1,42,'N');
INSERT INTO LINK VALUES (13,4,1,35,'NE');
INSERT INTO LINK VALUES (14,3,2,30,'NE');
INSERT INTO LINK VALUES (15,4,2,34,'N');
INSERT INTO LINK VALUES (16,4,3,12,'W');

COMMIT;

SELECT LEVEL,
       CONNECT_BY_ROOT(city_1) startcity,
       CITY_1 actcity, 
       SYS_CONNECT_BY_PATH(ID_LINK,'=>') links,
       SYS_CONNECT_BY_PATH(CITY_1,'->') way,
       SYS_CONNECT_BY_PATH(NVL(PRIOR DISTANCE,0),'+') dist,
       XMLQUERY(SYS_CONNECT_BY_PATH(NVL(PRIOR DISTANCE,0),'+') RETURNING CONTENT).getNumberVal() sumdist,
       CONNECT_BY_ISLEAF  
 FROM LINK
 CONNECT BY NOCYCLE
  (PRIOR CITY_2 = CITY_1 AND PRIOR ID_LINK ! = ID_LINK AND LEVEL <= 4 ) 
  --START WITH CITY_1 = 1
ORDER BY sumdist;

LEVEL STARTCITY ACTCITY LINKS         	WAY             DIST          SUMDIST CBL
-----------------------------------------------------------------------------------------
1	1	1	=>1	    	->1		+0		0	0
1	1	1	=>2	    	->1		+0		0	0
...
4	4	1	=>16=>14=>11=>1	->4->3->2->1	+0+12+30+20	62	1

This version is very stupid and ressource hungry and will calclulate all possible ways over and over.
In the end you have to find the shortest way with all visited points - here ->4->3->2->1 with sumdist 62 (and backwards).
Previous Topic: PLSQL Code: Error: PLS-00487: Invalid reference to variable
Next Topic: invalid rowid
Goto Forum:
  


Current Time: Thu Apr 24 09:41:34 CDT 2014

Total time taken to generate the page: 0.18164 seconds