Dijkstra's Algoritm Problem
Mar 5, 2007
I want to make it possible that I can see the path from one user to another and via whom the route went:
I want to pass the startnode and the endnode and then retreive the route between them.
In case I go from 5 to 15 (see table below), I want to have the following returned:
5-6-15
5-7-15
In case I go from 5 to 18 I want to have returned:
5-6-15-9-18
5-7-15-9-18
always up to a maximum distance of 6 steps.
I have the following table definition
tblFriends
OwnerCode int
FriendCode int
this table contains content like:
5
6
5
11
5
7
6
5
6
12
6
15
6
11
7
15
7
5
9
15
9
18
11
5
11
6
12
6
13
6
15
6
15
7
15
9
18
9
As you can see, I store each relationship twice.
I have created the following SP to retreive the info, but dont know how I can get from these results to the results I desire as described above....
STORED PROCEDURE
set ANSI_NULLS ON
set QUOTED_IDENTIFIER ON
go
ALTER PROCEDURE [dbo].[myspShortestPath]
--shortest path based on algorythm of Dijkstra
@ViewingUserCode int,
@ViewedUserCode int,
@MaxDistance int=100,
@MinDistance int
AS
BEGIN
-- Automatically rollback the transaction if something goes wrong.
SET XACT_ABORT ON
BEGIN TRAN
-- SET NOCOUNT ON added to prevent extra result sets from
-- interfering with SELECT statements.
SET NOCOUNT ON;
-- Create a temporary table for storing the estimates as the algorithm runs
CREATE TABLE #UserList
(
UserCode Int NOT NULL, -- The City Id
UserName nvarchar(50),
Estimate Int NOT NULL, -- What is the distance to this city, so far?
Predecessor nvarchar(max), -- The city we came from to get to this city with this distance.
PredecessorCodes nvarchar(max),
Done bit NOT NULL -- Are we done with this city yet (is the estimate the final distance)?
)
-- Fill the temporary table with initial data
INSERT INTO #UserList (UserCode, UserName, Estimate, Predecessor,PredecessorCodes, Done)
SELECT UserCode, UserName, 2147483647, '', '', 0 FROM tblUserData
-- Set the estimate for the city we start in to be 0.
UPDATE #UserList SET Estimate = 0 WHERE UserCode = @ViewingUserCode
IF @@rowcount <> 1
BEGIN
RAISERROR ('Couldn''t set start user', 11, 1)
ROLLBACK TRAN
RETURN
END
DECLARE @FromUser Int, @CurrentEstimate Int,@FromUserName nvarchar(50)
-- Run the algorithm until we decide that we are finished
WHILE 1=1
BEGIN
-- Reset the variable, so we can detect getting no records in the next step.
SELECT @FromUser = NULL
-- Select the UserCode and current estimate for a city not done, with the lowest estimate.
SELECT TOP 1 @FromUser = UserCode, @FromUserName = UserName, @CurrentEstimate = Estimate
FROM #UserList WHERE Done = 0 AND Estimate < 2147483647
-- Stop if we have no more unvisited, reachable cities.
IF @FromUser IS NULL BREAK
-- We are now done with this city.
UPDATE #UserList SET Done = 1 WHERE UserCode = @FromUser
-- Update the estimates to all neighbour cities of this one (all the cities
-- there are roads to from this city). Only update the estimate if the new
-- proposal (to go via the current city) is better (lower).
UPDATE #UserList SET #UserList.Estimate = @CurrentEstimate + 1,
--keep the other predecessors as well
#UserList.Predecessor = replace(@FromUserName, ' ', '')+','+#UserList.Predecessor,
#UserList.PredecessorCodes = replace(str(@FromUser), ' ', '')+','+#UserList.PredecessorCodes
FROM #UserList INNER JOIN tblFriends ON #UserList.UserCode = tblFriends.UserCodeFriend
WHERE tblFriends.UserCodeOwner = @FromUser AND (@CurrentEstimate + 1) <= #UserList.Estimate
END
SELECT ud1.UserName AS UserNameFriend,ud1.UserCode, Estimate AS Distance, PredecessorCodes, Predecessor
FROM #UserList
INNER JOIN tblUserData ud1 ON #UserList.UserCode = ud1.UserCode
WHERE #UserList.Estimate<=@MaxDistance AND #UserList.Estimate>=@MinDistance
ORDER BY Distance ASC
-- Drop the temp table.
DROP TABLE #UserList
COMMIT TRAN
END
View 2 Replies
Feb 6, 2004
We are in need of finalizing an archival approach for one of our Web and Client server application. The major requirements are
a) User can click on Web front end to start archival process.
b) The system should move the related data to archived space in a backup location.
c) Could be a batch process.
d) The relation between tables is extensive i.e. > 30 tables need to be managed for archival one component.
e) Database size is not very huge < 10 MB.
We were planning to have a table to store archival flag, which will be set when user click on Archival. Then a batch program will copy the database in to a backup location and delete the entries from archived database where archive flag is not set and delete entry from master database where archive flag is set. The problem is how to synchronize the changes when archival process runs next time i.e. the master database would have changed so how to put that data in archival database with out removing existing data.
Any other approach/practical solutions will be very helpful.
Regards,
Mridul Mishra
View 2 Replies
View Related
Jan 8, 2007
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 outputFromToCost
----------
ab 4
bc 6
cj18
jf26
fi37
Peter Larsson
Helsingborg, Sweden
View 20 Replies
View Related
Jan 9, 2008
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 feel forced to 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 example 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 JohnWhen 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 Jack6 John 15 Hans 48 JackWhen 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 col85 Peter 11 Hans 48 Jack 51 AndreIn any case when there are multiple paths from person A to person B, I only want the shortest paths returned to a maximum of 4Since 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)
View 2 Replies
View Related