Thursday, March 22, 2012

dijkstras algoritm problem

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:

56511576561261561171575915918115116126136156157159189


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

Check if this helps:http://hansolav.net/blog/CommentView,guid,1dfcc780-268a-415e-ae1f-aa20f370677e.aspx|||thats what I derived my sp from in the first place :)sql

No comments:

Post a Comment