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:
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