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


ADVERTISEMENT

Archival Logic/algoritm

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

Dijkstra's Shortest Path Algorithm

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

EXPERT: Implement Dijkstra's Algorithm -&> Need Lots Of Help Implementing!

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







Copyrights 2005-15 www.BigResource.com, All rights reserved