expert: implement Dijkstra's algorithm (advanced)

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

SQL Server 2005 Forums

Transact-SQL (2005)

expert: implement Dijkstra's algorithm (advanced)

Author

Topic

Peter Smith
Starting Member

8 Posts

Posted - 2008-01-17 : 18:35:49

This is such a complex question and I'm 99.9% sure it requires usage of Dijkstra's algorithm in order to determine the shortest path

I have tried to build this myself (yes, I've viewed enough examples on the web, but since they dont exactly do what I want AND I'm rather new to this advanced SQL AND my boss would really like this asap I call upon the community)

Basically I need a query which analyzes the relationships between 2 persons and returns the shortest path(S!) I have provided the data that is required to perform any tests below. The examples I provide match with the given data.

I know for sure that such a query has been written before since for example LinkedIN uses something similar...so if anyone has this off the shelf for me great!
If not, I would really really appreciate it if someone could provide a completely worked out example. I'll even give special thanks to that person on our future website :)
So, many thanks ahead for whoever takes up this challenge! :)

CASE:
-----------------------------------------------------------------------------
I have tables with friend relationships and tables with userdata.

Lets say im logged in as Peter (usercode 5).
Now if I (as user Peter) view the profile of Andre (usercode 51), I want to determine the relationship that exists between me and Andre.

When the users would have a direct relationship, eg. between Peter (5) and John (6) I want returned:
col1 col2 col3 col4
5 Peter 6 John

When the users would have a indirect relationship, witch EXACTLY 1 person in between, like between John (6) and Jack (48).
So I can go from John to Jack in exactly 2 steps via multiple persons, in this case I want the following rows returned (max 4):
col1 col2 col3 col4 col5 col6
6 John 11 Hans 48 Jack
6 John 15 Hans 48 Jack

When the users would have a indirect relationship, witch MORE than 1 persons in between, like between Peter (5) and Andre (48), I want returned:
col1 col2 col3 col4 col5 col6 col7 col8
5 Peter 11 Hans 48 Jack 51 Andre

In any case when there are multiple paths from person A to person B, I only want the shortest paths returned to a maximum of 4
Since this query will be called may times by different users at the same time concurrency issues also need to be taken into account (e.g. usage of temp tables)

with the entire query the maximum amount of steps that should be checked is 6, so maximum 6 persons in between 2 persons.
So if a viewed user is more than 6 steps away from the viewing user I want no results returned.
E.g. when Peter (5) views the profile of Simon (7), no relationship exists through any other person, and an empty dataset should be returned.

-----------------------------------------------------------------------------

I have the following tables and data:

CREATE TABLE [dbo].[tblFriends](
[UserCodeOwner] [int] NOT NULL,
[UserCodeFriend] [int] NOT NULL,
[createdate] [datetime] NOT NULL CONSTRAINT [DF_tblFriends_createdate] DEFAULT (getdate())
) ON [PRIMARY]

CREATE TABLE [dbo].[tblUserData](
[UserID] [uniqueidentifier] NOT NULL,
[UserCode] [int] IDENTITY(1,1) NOT NULL,
[UserName] [nvarchar](50) COLLATE SQL_Latin1_General_CP1_CI_AS NOT NULL,
[DisplayName] [nvarchar](50) COLLATE SQL_Latin1_General_CP1_CI_AS NULL,

) ON [PRIMARY]

INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (5,'peter',':-D Peter ;-)')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (6,'john','J ;-)')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (7,'simon','Simon :-D')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (11,'hans','Hans :-)')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (15,'Jane','Jane3')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (28,'jean','jean')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (48,'Jack','Jack')
INSERT INTO tblUserdata (UserCode,UserName,DisplayName) VALUES (51,'Andre','Andre')

INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (5,11)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (5,6)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (6,11)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (6,5)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (6,15)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (7,28)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (11,6)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (11,5)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (11,15)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (11,48)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (15,6)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (15,11)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (15,48)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (28,7)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (48,11)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (48,51)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (48,15)
INSERT INTO tblFriends (UserCodeOwner,UserCodeFriend) VALUES (51,48)

To that one person who can fix this: my eternal thanks! :)

Peter

graz
Chief SQLTeam Crack Dealer

4149 Posts

Posted - 2008-01-17 : 18:40:42

Did you see our thread on this? http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=77262

=================================================
Creating tomorrow's legacy systems today. One crisis at a time.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2008-01-18 : 02:07:29

Dijkstra's algorithm is not necessary here sinve you have no cost for travelling the different paths.

Also see
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079

E 12°55'05.25"
N 56°04'39.16"

Peter Smith
Starting Member

8 Posts

Posted - 2008-01-18 : 04:31:51

Hi Peso,

Thank you for your links. I read them both and must say that im starting to get happier that Dijkstra's algorythm is not required.

However, these examples have the realtionships between to persons stored ONCE in the table:
ab
bc
ca

where as I store relationships twice:
ab
ac
ba
bc
ca
cb

My output is also different: when I ask for the relationships between 2 persons, I want a maximum of 3 shortest paths (equally in length).
AND I want my query to return only results if the travelled path is no more than 6 steps in between

Are you willing to help me on that?

Thanks in advance!

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources