---Create tables
drop table ROUTES
go
drop table CITIES
go

create table CITIES (
    NAME varchar(30) primary key
)
go

create table ROUTES (
    FROM_CITY varchar(30) references CITIES,
    TO_CITY varchar(30) references CITIES,
    MILES float not null,
    primary key (from_city, to_city)
)
go


---Create view to show all routes, because it is an undirected graph
drop view ALL_ROUTES
go
create view ALL_ROUTES (FROM_CITY, TO_CITY, MILES) as 
    select FROM_CITY, TO_CITY, MILES from ROUTES
    union
    select TO_CITY, FROM_CITY, MILES from ROUTES
go


---Procedure to rotate values in #array to create all permutations of the possible paths 
---		using all cities except the startCity
drop procedure rotate
go
create procedure rotate @count int
as
	---Declare temp variable
	declare @temp varchar(30), @i int
	---Save first value
	set @temp = (select NAME from #array where id = 1)
	set @i = 0
	
	---Shift all values to the left
	while (@i < @count) begin
		update #array set ID = @i where ID = @i + 1
		set @i = @i + 1
	end
	
	---Add temp value to the end
	update #array set ID = @count where ID = 0
go


---Procedure to test and save permutation if it is a good route that exists
drop procedure savePerm
go
create procedure savePerm @count int, @startCity varchar(30)
as
	---Allow for @startCity at beginning of route
	set @count = @count + 1
	---Declare and initialize needed variables
	declare @i int, @value varchar(1000), @prevCity varchar(30), 
		@nextCity varchar(30), @totalMiles int, @currentMiles int, @goodRoute int, @numRoutes int	
	set @i = 1
	set @value = @startCity
	set @prevCity = @startCity
	set @nextCity = (select NAME from #array where ID = 1)	
	set @totalMiles = 0
	set @currentMiles = 0	
	set @goodRoute = 1	
	
	---Loop through permutation array
	while (@i < @count) begin
		set @i = @i + 1
		---See if such a path exists in the routes table
		set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity)
		---If a path exists
		if @numRoutes > 0 begin
			---Get the number of miles and add to total miles
			set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @nextCity)
			set @totalMiles = @totalMiles + @currentMiles
			---Store good route
			set @value = @value + '->' + @nextCity
			---Get next city in permutation array
			set @prevCity = @nextCity
			set @nextCity = (select NAME from #array where ID = @i)	
		end
		---If no path exists
		else begin
			---This route is no good, set the exit condition to exit the loop
			set @goodRoute = 0
			set @i = @count
		end
	end
	
	---One more time to add @startCity to end of route
	set @numRoutes = (select COUNT(*) from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity)
	if @numRoutes > 0 begin
		set @currentMiles = (select MILES from ALL_ROUTES where FROM_CITY = @prevCity and TO_CITY = @startCity)
		set @totalMiles = @totalMiles + @currentMiles
		set @value = @value + '->' + @startCity
	end
	else begin
		set @goodRoute = 0
	end

	---If got this far and route is good, save to perms table
	if @goodRoute = 1 begin
		insert into #perms values(@value, @totalMiles)
	end
go


---Recursive procedure to create all possible permutations of the possible paths 
---		using all cities except the startCity
drop procedure permute
go
create procedure permute @size int, @n int, @startCity varchar(30), @val1 varchar(30), @val2 varchar(30)
as
	---Declare and initialize neede variables
	declare @i int, @permuteVar int, @rotateVar int, @val1pos int, @val2pos int, @max int
	set @i = @size - @n
	
	---If a permutation is ready for checking call savePerm
	if @size = @n begin
		---Limit to half of permutations, 
		---		only care about routes where arbitrary city 1 is before arbitrary city 2
		set @val1pos = (select ID from #array where NAME = @val1)
		set @val2pos = (select ID from #array where NAME = @val2)		
		if (@val1pos < @val2pos) begin	
			exec savePerm @size, @startCity
		end
	end
	else begin
		---Recursively call itself and then rotate values in array to generate all permutations
		while (@i > 0) begin
			set @permuteVar = @n + 1
			exec permute @size, @permuteVar, @startCity, @val1, @val2
			set @rotateVar = @size - @n
			exec rotate @rotateVar
			set @i = @i - 1
		end
	end
go


---Main procedure to get answer for TSP route
drop procedure getTSPRoute
go
create procedure getTSPRoute @startCity varchar(30)
as
	---Create array of cities, 
	---		needs AUTO_ID and ID because rotate function wont work with IDENTITY column
	create table #array (AUTO_ID int identity, ID int, NAME varchar(30))
	insert into #array select 0, NAME FROM cities where NAME <> @startCity
	update #array set ID = AUTO_ID

	---Create table to store good permutations
	create table #perms (ROUTE_PATH varchar(1000), MILES int)
	
	---Get 2 arbitrary cities, so that only routes where city 1 is before city 2 will be looked at
	declare @val1 varchar(30), @val2 varchar(30), @size int
	set @val1 = (select top 1 NAME from CITIES where NAME <> @startCity order by name)
	set @val2 = (select top 1 NAME from CITIES where NAME <> @startCity order by name desc)
	
	---Get size of city array for number of cities
	set @size = (select COUNT(*) from #array)
	
	---Call recursive permute function to generate all possible permutations of the possible paths 
	---		using all cities except the startCity
	exec permute @size, 0, @startCity, @val1, @val2
	
	---When done select the shortest route from the perms table of good routes
	select ROUTE_PATH, MIN(MILES) as MILES from #perms group by ROUTE_PATH having MIN(MILES) = (select MIN(miles) from #perms)
go

---**************************************************************************************************************************

--- Test attempt 1
--- 5 cities
--- Running time: 2 seconds

delete from routes
delete from cities
insert into cities values ('A')
insert into cities values ('B')
insert into cities values ('C')
insert into cities values ('D')
insert into cities values ('E')
insert into routes values ('A', 'B', 5)
insert into routes values ('A', 'C', 20)
insert into routes values ('A', 'D', 28.28)
insert into routes values ('A', 'E', 20)
insert into routes values ('B', 'C', 15)
insert into routes values ('B', 'D', 25)
insert into routes values ('B', 'E', 20.62)
insert into routes values ('C', 'D', 20)
insert into routes values ('C', 'E', 28.28)
insert into routes values ('D', 'E', 20)
go

exec getTSPRoute 'A'

---**************************************************************************************************************************

--- Test attempt 2
--- 8 cities
--- Running time: 5 seconds

delete from routes
delete from cities
insert into cities values ('A')
insert into cities values ('B')
insert into cities values ('C')
insert into cities values ('D')
insert into cities values ('E')
insert into cities values ('F')
insert into cities values ('G')
insert into cities values ('H')
insert into routes values ('A', 'B', 200)
insert into routes values ('B', 'C', 300)
insert into routes values ('C', 'D', 200)
insert into routes values ('D', 'E', 300)
insert into routes values ('E', 'F', 100)
insert into routes values ('F', 'G', 200)
insert into routes values ('G', 'H', 250)
insert into routes values ('H', 'A', 250)
insert into routes values ('D', 'F', 200)
insert into routes values ('E', 'G', 250)
insert into routes values ('A', 'E', 50)
insert into routes values ('B', 'E', 50)
go

exec getTSPRoute 'A'

---**************************************************************************************************************************

--- Test attempt 3
--- 9 cities
--- Running time: 41 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
go

exec getTSPRoute 'New York'

---**************************************************************************************************************************

--- Test attempt 4
--- 10 cities
--- Running time: 6 minutes 34 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Miami')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('Miami', 'Washington', 900)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Miami', 1050)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
insert into routes values ('Miami', 'Dallas', 1100)
go

exec getTSPRoute 'New York'

---**************************************************************************************************************************

--- Test attempt 5
--- 11 cities
--- Running time: 1 hr 30 mins 43 seconds

delete from routes
delete from cities
insert into cities values ('New York')
insert into cities values ('Washington')
insert into cities values ('Miami')
insert into cities values ('Chicago')
insert into cities values ('St. Louis')
insert into cities values ('Dallas')
insert into cities values ('Denver')
insert into cities values ('Phoenix')
insert into cities values ('Los Angeles')
insert into cities values ('San Francisco')
insert into cities values ('Seattle')
insert into routes values ('New York', 'Washington', 200)
insert into routes values ('New York', 'Chicago', 700)
insert into routes values ('Miami', 'Washington', 900)
insert into routes values ('St. Louis', 'Washington', 700)
insert into routes values ('St. Louis', 'Miami', 1050)
insert into routes values ('St. Louis', 'Chicago', 250)
insert into routes values ('St. Louis', 'Dallas', 550)
insert into routes values ('St. Louis', 'Denver', 800)
insert into routes values ('Chicago', 'Denver', 900)
insert into routes values ('Seattle', 'Denver', 1000)
insert into routes values ('San Francisco', 'Denver', 950)
insert into routes values ('San Francisco', 'Seattle', 700)
insert into routes values ('San Francisco', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Los Angeles', 350)
insert into routes values ('Phoenix', 'Dallas', 900)
insert into routes values ('Miami', 'Dallas', 1100)
go

exec getTSPRoute 'New York'

quote:

---

Originally posted by tkizer

Your code looks like T-SQL and not PL/SQL. Are you sure this was for Oracle and not Microsoft SQL Server? It makes a difference here since SQLTeam.com is for MSSQL.

Tara Kizer
Microsoft MVP for Windows Server System - SQL Server
http://weblogs.sqlteam.com/tarad/

Subscribe to my blog

---

SET NOCOUNT ON;

-- Prepare sample data
CREATE TABLE	#Nodes
		(
			Name VARCHAR(30) PRIMARY KEY CLUSTERED
		);


INSERT	#Nodes
	(
		Name
	)
VALUES	('New York'),
	('Washington'),
	('Miami'),
	('Chicago'),
	('St. Louis'),
	('Dallas'),
	('Denver'),
	('Phoenix'),
	('Los Angeles'),
	('San Francisco'),
	('Seattle');

CREATE TABLE	#Routes
		(
			FromNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name),
			ToNode VARCHAR(30) NOT NULL REFERENCES #Nodes(Name),
			Distance DECIMAL(28, 12) NOT NULL,
			PRIMARY KEY CLUSTERED
			(
				FromNode,
				ToNode
			)
		);

INSERT	#Routes
	(
		FromNode,
		ToNode,
		Distance
	)
OUTPUT	inserted.ToNode AS FromNode,
	inserted.FromNode AS ToNode,
	inserted.Distance
INTO	#Routes
	(
		FromNode,
		ToNode,
		Distance
	)
VALUES	('New York', 'Washington', 200),
	('New York', 'Chicago', 700),
	('Miami', 'Washington', 900),
	('St. Louis', 'Washington', 700),
	('St. Louis', 'Miami', 1050),
	('St. Louis', 'Chicago', 250),
	('St. Louis', 'Dallas', 550),
	('St. Louis', 'Denver', 800),
	('Chicago', 'Denver', 900),
	('Seattle', 'Denver', 1000),
	('San Francisco', 'Denver', 950),
	('San Francisco', 'Seattle', 700),
	('San Francisco', 'Los Angeles', 350),
	('Phoenix', 'Los Angeles', 350),
	('Phoenix', 'Dallas', 900),
	('Miami', 'Dallas', 1100);

-- Solution
DECLARE	@Nodes INT = (SELECT COUNT(*) FROM #Nodes);

WITH cteMap(Nodes, LastNode, Distance, NodeMap)
AS (
	SELECT	2 AS Nodes,
		ToNode,
		Distance,
		CAST('\' + FromNode + '\' + ToNode + '\' AS VARCHAR(MAX)) AS NodeMap
	FROM	#Routes

	UNION ALL

	SELECT		m.Nodes + 1 AS Nodes,
			r.ToNode AS LastNode,
			CAST(m.Distance + r.Distance AS DECIMAL(28, 12)) AS Distance,
			CAST(m.NodeMap + r.ToNode + '\' AS VARCHAR(MAX)) AS NodeMap
	FROM		cteMap AS m
	INNER JOIN	#Routes AS r ON r.FromNode = m.LastNode
	WHERE		m.NodeMap NOT LIKE '\%' + r.ToNode + '%\'
)
SELECT	TOP(1)
WITH	TIES	Distance,
		NodeMap
FROM		cteMap
WHERE		Nodes = @Nodes
ORDER BY	Distance DESC
OPTION		(MAXRECURSION 0);

-- Clean up
DROP TABLE	#Routes,
		#Nodes;

quote:

---

Originally posted by AnthonyNedu

Swepeso, please can you give me your email so that I can contact you concerning a travel salesman problem, or you can contact me on tzamanda@yahoo.com
Thanks

---