SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 General SQL Server Forums
 Script Library
 Dijkstra's Shortest Path Algorithm
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  08:19:48  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Here it is, the long lasted algorithm I promised..,
-- delete previous map
exec dbo.uspdijkstrainitializemap

-- create a new map
exec dbo.uspdijkstraaddpath 'a', 'b',  4
exec dbo.uspdijkstraaddpath 'a', 'd',  1
exec dbo.uspdijkstraaddpath 'b', 'a', 74
exec dbo.uspdijkstraaddpath 'b', 'c',  2
exec dbo.uspdijkstraaddpath 'b', 'e', 12
exec dbo.uspdijkstraaddpath 'c', 'b', 12
exec dbo.uspdijkstraaddpath 'c', 'f', 74
exec dbo.uspdijkstraaddpath 'c', 'j', 12
exec dbo.uspdijkstraaddpath 'd', 'e', 32
exec dbo.uspdijkstraaddpath 'd', 'g', 22
exec dbo.uspdijkstraaddpath 'e', 'd', 66
exec dbo.uspdijkstraaddpath 'e', 'f', 76
exec dbo.uspdijkstraaddpath 'e', 'h', 33
exec dbo.uspdijkstraaddpath 'f', 'i', 11
exec dbo.uspdijkstraaddpath 'f', 'j', 21
exec dbo.uspdijkstraaddpath 'g', 'd', 12
exec dbo.uspdijkstraaddpath 'g', 'h', 10
exec dbo.uspdijkstraaddpath 'h', 'g',  2
exec dbo.uspdijkstraaddpath 'h', 'i', 72
exec dbo.uspdijkstraaddpath 'i', 'f', 31
exec dbo.uspdijkstraaddpath 'i', 'j',  7
exec dbo.uspdijkstraaddpath 'i', 'h', 18
exec dbo.uspdijkstraaddpath 'j', 'f',  8

-- resolve route
exec dbo.uspdijkstraresolve 'a', 'i'
This is the output
From	To	Cost
----	--	----
a	b	 4
b	c	 6
c	j	18
j	f	26
f	i	37


Peter Larsson
Helsingborg, Sweden

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  08:21:46  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Here is the DDL...
CREATE TABLE [dbo].[Nodes] (
	[NodeID] [int] IDENTITY (1, 1) NOT NULL ,
	[NodeName] [varchar] (20) COLLATE Finnish_Swedish_CI_AS NOT NULL ,
	[Cost] [int] NULL ,
	[PathID] [int] NULL ,
	[Calculated] [tinyint] NOT NULL 
) ON [PRIMARY]
GO

CREATE TABLE [dbo].[Paths] (
	[PathID] [int] IDENTITY (1, 1) NOT NULL ,
	[FromNodeID] [int] NOT NULL ,
	[ToNodeID] [int] NOT NULL ,
	[Cost] [int] NOT NULL 
) ON [PRIMARY]
GO

ALTER TABLE [dbo].[Nodes] WITH NOCHECK ADD 
	CONSTRAINT [PK_Nodes] PRIMARY KEY  CLUSTERED 
	(
		[NodeID]
	)  ON [PRIMARY] 
GO

ALTER TABLE [dbo].[Paths] WITH NOCHECK ADD 
	CONSTRAINT [PK_Paths] PRIMARY KEY  CLUSTERED 
	(
		[PathID]
	)  ON [PRIMARY] 
GO

ALTER TABLE [dbo].[Paths] ADD 
	CONSTRAINT [FK_Paths_FromNodes] FOREIGN KEY 
	(
		[FromNodeID]
	) REFERENCES [dbo].[Nodes] (
		[NodeID]
	),
	CONSTRAINT [FK_Paths_ToNodes] FOREIGN KEY 
	(
		[ToNodeID]
	) REFERENCES [dbo].[Nodes] (
		[NodeID]
	)
GO

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 03/24/2007 15:00:41
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  08:24:49  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Here are some stored procedures...
CREATE PROCEDURE dbo.uspDijkstraInitializeMap
AS

DELETE
FROM	Paths

DBCC CHECKIDENT (Paths, RESEED, 0)

DELETE
FROM	Nodes

DBCC CHECKIDENT (Nodes, RESEED, 0)
GO

CREATE PROCEDURE dbo.uspDijkstraClearMap
AS

UPDATE	Nodes
SET	PathID = NULL,
	Cost = NULL,
	Calculated = 0
GO

CREATE PROCEDURE dbo.uspDijkstraAddPath
(
	@FromNodeName VARCHAR(20),
	@ToNodeName VARCHAR(20),
	@Cost INT
)
AS

SET NOCOUNT ON

DECLARE	@FromNodeID INT,
	@ToNodeID INT,
	@PathID INT

SELECT	@FromNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @FromNodeName

IF @FromNodeID IS NULL
	BEGIN
		INSERT	Nodes
			(
				NodeName,
				Calculated
			)
		VALUES	(
				@FromNodeName,
				0
			)

		SELECT	@FromNodeID = SCOPE_IDENTITY()
	END

SELECT	@ToNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @ToNodeName

IF @ToNodeID IS NULL
	BEGIN
		INSERT	Nodes
			(
				NodeName,
				Calculated
			)
		VALUES	(
				@ToNodeName,
				0
			)

		SELECT	@ToNodeID = SCOPE_IDENTITY()
	END

SELECT	@PathID = PathID
FROM	Paths
WHERE	FromNodeID = @FromNodeID
	AND ToNodeID = @ToNodeID

IF @PathID IS NULL
	INSERT	Paths
		(
			FromNodeID,
			ToNodeID,
			Cost
		)
	VALUES	(
			@FromNodeID,
			@ToNodeID,
			@Cost
		)
ELSE
	UPDATE	Paths
	SET	Cost = @Cost
	WHERE	FromNodeID = @FromNodeID
		AND ToNodeID = @ToNodeID
GO


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  08:27:50  Show Profile  Visit SwePeso's Homepage  Reply with Quote
And of course the route resolving algorithm...
CREATE PROCEDURE dbo.uspDijkstraResolve
(
	@FromNodeName VARCHAR(20),
	@ToNodeName VARCHAR(20)
)
AS

SET NOCOUNT ON

EXEC dbo.uspDijkstraClearMap

DECLARE	@FromNodeID INT,
	@ToNodeID INT,
	@NodeID INT,
	@Cost INT,
	@PathID INT

SELECT	@FromNodeID = NodeID,
	@NodeID = NodeID
FROM	Nodes
WHERE	NodeName = @FromNodeName

IF @FromNodeID IS NULL
	BEGIN
		SELECT	@FromNodeName = ISNULL(@FromNodeName, '')
		RAISERROR ('From node name ''%s'' can not be found.', 16, 1, @FromNodeName) 
		RETURN
	END

SELECT	@ToNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @ToNodeName

IF @ToNodeID IS NULL
	BEGIN
		SELECT	@ToNodeName = ISNULL(@ToNodeName, '')
		RAISERROR ('To node name ''%s'' can not be found.', 16, 1, @ToNodeName) 
		RETURN
	END

UPDATE	Nodes
SET	Cost = 0
WHERE	NodeID = @FromNodeID

WHILE @NodeID IS NOT NULL
	BEGIN
		UPDATE		ToNodes
		SET		ToNodes.Cost =	CASE
							WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
							WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
							ELSE ToNodes.Cost
						END,
				ToNodes.PathID = Paths.PathID
		FROM		Nodes AS FromNodes
		INNER JOIN	Paths ON Paths.FromNodeID = FromNodes.NodeID
		INNER JOIN	Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
		WHERE		FromNodes.NodeID = @NodeID
				AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
				AND ToNodes.Calculated = 0

		UPDATE	FromNodes
		SET	FromNodes.Calculated = 1
		FROM	Nodes AS FromNodes
		WHERE	FromNodes.NodeID = @NodeID

		SELECT	@NodeID = NULL

		SELECT TOP 1	@NodeID = Nodes.NodeID
		FROM		Nodes
		WHERE		Nodes.Calculated = 0
				AND Nodes.Cost IS NOT NULL
		ORDER BY	Nodes.Cost
	END

CREATE TABLE	#Map
		(
			RowID INT IDENTITY(-1, -1),
			FromNodeName VARCHAR(20),
			ToNodeName VARCHAR(20),
			Cost INT
		)

IF EXISTS (SELECT NULL FROM Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
	BEGIN
		SELECT	FromNodeName,
			ToNodeName,
			Cost
		FROM	#Map

		DROP TABLE #Map

		RETURN
	END

WHILE @FromNodeID <> @ToNodeID
	BEGIN
		SELECT		@FromNodeName = FromNodes.NodeName,
				@ToNodeName = ToNodes.NodeName,
				@Cost = ToNodes.Cost,
				@PathID = ToNodes.PathID
		FROM		Nodes AS ToNodes
		INNER JOIN	Paths ON Paths.PathID = ToNodes.PathID
		INNER JOIN	Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
		WHERE		ToNodes.NodeID = @ToNodeID

		INSERT	#Map
			(
				FromNodeName,
				ToNodeName,
				Cost
			)
		VALUES	(
				@FromNodeName,
				@ToNodeName,
				@Cost
			)

		SELECT	@ToNodeID = Paths.FromNodeID
		FROM	Paths
		WHERE	Paths.PathID = @PathID
	END

SELECT		FromNodeName,
		ToNodeName,
		Cost
FROM		#Map
ORDER BY	RowID

DROP TABLE #Map
GO

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 01/09/2007 16:01:13
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  09:02:41  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You can use this page http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html to verify the result or calculating a new route.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  09:16:50  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Yes, I know

exec dbo.uspdijkstraresolve 'e', 'c'
exec dbo.uspdijkstraresolve 'g', 'b'

will produce an empty resultset, but that is because the route is not solvable.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 01/08/2007 09:33:38
Go to Top of Page

Kristen
Test

United Kingdom
22403 Posts

Posted - 01/08/2007 :  12:29:25  Show Profile  Reply with Quote
I was just about to point that out ...
Go to Top of Page

spirit1
Cybernetic Yak Master

Slovenia
11751 Posts

Posted - 01/08/2007 :  12:52:22  Show Profile  Visit spirit1's Homepage  Reply with Quote
AWSOME!!!



Go with the flow & have fun! Else fight the flow
blog thingie: http://weblogs.sqlteam.com/mladenp
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  13:12:36  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Thanks.
I hope you like it Spirit, becuase you asked for the algorithm.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

spirit1
Cybernetic Yak Master

Slovenia
11751 Posts

Posted - 01/08/2007 :  13:21:27  Show Profile  Visit spirit1's Homepage  Reply with Quote
maybe my enthusiasm wasn't clear enough:
AAAAAAAAAA WWWWWWWWWWW SSSSSSSSSSS OOOOOOOO MMMMMMMM EEEEEEEEEE !!!!!!!!!!!!!!!!





Go with the flow & have fun! Else fight the flow
blog thingie: http://weblogs.sqlteam.com/mladenp
Go to Top of Page

Michael Valentine Jones
Yak DBA Kernel (pronounced Colonel)

USA
7020 Posts

Posted - 01/08/2007 :  13:42:49  Show Profile  Reply with Quote
So, what would you use this for?


CODO ERGO SUM
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/08/2007 :  13:57:17  Show Profile  Visit SwePeso's Homepage  Reply with Quote
One of the purposes I have used this for is in a contact management system (with some changes of course) to see how far apart people are, or know each other, like "friend-of-a-friend-of-a-friend".

More specialized attempts are found here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079

The difference with these two examples are that all paths always has a cost of 1 and treated as "two-way" path (If person A knows person B, then person B also knows person A).

With the general algorithm above, not only is it possible to enter connections as "person A knows person B, but person B does not know person A". Also, you can enter how well people know each other.

Person A is brother to person B, then enter "cost" of 1 (know very well).
Person C went to same high school as person D. Enter a cost of 10 (know of).

Cost can also be a source of trust level!
Person A trust person B very much (cost is 1), but person B does not trust person A very much (cost is 5), even if they know each other.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 01/08/2007 19:11:38
Go to Top of Page

jezemine
Flowing Fount of Yak Knowledge

USA
2886 Posts

Posted - 01/08/2007 :  19:07:23  Show Profile  Visit jezemine's Homepage  Reply with Quote
That's quite something! I've implemented this algorithm before in C++, but I never would have thought to do it in SQL.



www.elsasoft.org
Go to Top of Page

harsh_athalye
Flowing Fount of Yak Knowledge

India
5528 Posts

Posted - 01/09/2007 :  01:08:28  Show Profile  Visit harsh_athalye's Homepage  Click to see harsh_athalye's MSN Messenger address  Send harsh_athalye a Yahoo! Message  Reply with Quote
Amazing!!

Found that this topic is already linked to Wikipedia.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

So what's next, Peter? Graph algorithms?

Harsh Athalye
India.
"The IMPOSSIBLE is often UNTRIED"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/09/2007 :  04:44:34  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You mean like Fourier transformations?


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

harsh_athalye
Flowing Fount of Yak Knowledge

India
5528 Posts

Posted - 01/09/2007 :  04:54:27  Show Profile  Visit harsh_athalye's Homepage  Click to see harsh_athalye's MSN Messenger address  Send harsh_athalye a Yahoo! Message  Reply with Quote
I don't know. But frankly will anybody choose T-SQL as a language for its implementation, because it is purely mathematical topic and can be best handled in procedural languages.

Harsh Athalye
India.
"The IMPOSSIBLE is often UNTRIED"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/09/2007 :  05:07:52  Show Profile  Visit SwePeso's Homepage  Reply with Quote
I think that depends on the implementation.
A good implementaition in SQL will outperform a bad implementation in front-end application.

There are a number of regression methods that easily can be implemented in SQL, and better I think than front-end, since SQL Server is setbased.

I think I will try to implement a easiest one, the linear regression.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/09/2007 :  08:03:36  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Now it's done here http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77311

It wasn't that difficult and I included three more types.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 01/09/2007 08:04:40
Go to Top of Page

jezemine
Flowing Fount of Yak Knowledge

USA
2886 Posts

Posted - 01/09/2007 :  12:16:55  Show Profile  Visit jezemine's Homepage  Reply with Quote
quote:
Originally posted by Peso

You mean like Fourier transformations?


Peter Larsson
Helsingborg, Sweden



eh, that's child's play. I think you better do the Traveling Salesman next.
It ought to be close to your heart:
http://www.tsp.gatech.edu/sweden/index.html


www.elsasoft.org

Edited by - jezemine on 01/09/2007 12:23:36
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30242 Posts

Posted - 01/17/2007 :  07:49:07  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Jezemine, this should be evidence of that the orignal Travelling Salesman problem is not solvable for all types of paths, ie has no general algorithm to solve all paths.

According to the original TSP, each and one city can only be visited once.

    A
    |
B - C - D


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

jezemine
Flowing Fount of Yak Knowledge

USA
2886 Posts

Posted - 01/17/2007 :  09:56:49  Show Profile  Visit jezemine's Homepage  Reply with Quote
First of all, I was only kidding. To try and solve TSP in SQL would not be an efficient use of your time. I have some experience in computational mathematics, I am pretty sure SQL is NOT the optimal language for this type of problem. :)

You are right about not all graphs having a sol'n in TSP. In real world applications of tsp however, you often have more freedom on how you are allowed to traverse the nodes. Like for a drill that needs to put millions of holes in a printed circuit board, what's the optimal way to visit each hole? the drill can move however it likes. it could go from a->b for example.

also, usually there is more than one way to get to a town. I guess if there is only one way, that town would be happily free of traveling salesmen!




www.elsasoft.org
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.12 seconds. Powered By: Snitz Forums 2000