Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 General SQL Server Forums
 Script Library
 Dijkstra's Shortest Path Algorithm

Author  Topic 

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-08 : 08:19:48
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

30421 Posts

Posted - 2007-01-08 : 08:21:46
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
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-08 : 08:24:49
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

30421 Posts

Posted - 2007-01-08 : 08:27:50
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
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-08 : 09:02:41
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

30421 Posts

Posted - 2007-01-08 : 09:16:50
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
Go to Top of Page

Kristen
Test

22859 Posts

Posted - 2007-01-08 : 12:29:25
I was just about to point that out ...
Go to Top of Page

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2007-01-08 : 12:52:22
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

30421 Posts

Posted - 2007-01-08 : 13:12:36
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

11752 Posts

Posted - 2007-01-08 : 13:21:27
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)

7020 Posts

Posted - 2007-01-08 : 13:42:49
So, what would you use this for?


CODO ERGO SUM
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-08 : 13:57:17
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
Go to Top of Page

jezemine
Master Smack Fu Yak Hacker

2886 Posts

Posted - 2007-01-08 : 19:07:23
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
Master Smack Fu Yak Hacker

5581 Posts

Posted - 2007-01-09 : 01:08:28
Amazing!!

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

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

30421 Posts

Posted - 2007-01-09 : 04:44:34
You mean like Fourier transformations?


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

harsh_athalye
Master Smack Fu Yak Hacker

5581 Posts

Posted - 2007-01-09 : 04:54:27
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

30421 Posts

Posted - 2007-01-09 : 05:07:52
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

30421 Posts

Posted - 2007-01-09 : 08:03:36
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
Go to Top of Page

jezemine
Master Smack Fu Yak Hacker

2886 Posts

Posted - 2007-01-09 : 12:16:55
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
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-01-17 : 07:49:07
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
Master Smack Fu Yak Hacker

2886 Posts

Posted - 2007-01-17 : 09:56:49
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
    Next Page

- Advertisement -