Shortest route, non-weighted and bidirectional

create table Friendship(id int identity(1,1) primary key, user1ID int, user2ID int)

Insert into Friendship
select 1, 2 Union all
select 3, 4 Union all
select 2, 5 Union all
select 4, 5 Union all
select 6, 7 Union all
select 8, 9 Union all
select 1, 5 Union all
select 6, 9 Union all
select 3, 7 Union all
select 7, 6

Exec dbo.usp_ShortestRoute 9, 1, 8

Create Procedure usp_ShortestRoute (@StartNode int, @EndNode int, @depth int = null)
as
Begin

Declare @routes Table (RouteMap varchar(150), EndNode int, depth Int)
Declare @isRouteFound bit, @rows int, @msg varchar(150), @activedepth int

Select @isRouteFound = 0, @activedepth = 1

if (@StartNode = @EndNode)
select @msg = 'Start and End node are same'
else if not exists (select top 1 Id from Friendship Where user1ID = @StartNode or user2ID = @StartNode)
or not exists (select top 1 Id from Friendship Where user1id = @endNode or user2ID = @EndNode)
select @msg = 'No possible Route'
else
Begin
Insert into @routes
select CAST(user1ID as varchar(3)) + ' - ' + CAST(user2ID as varchar(3)), user2ID, 1 from Friendship where user1ID = @StartNode
Union
select CAST(user2ID as varchar(3)) + ' - ' + CAST(user1ID as varchar(3)), user1ID, 1 from Friendship where user2ID = @StartNode

set @rows = @@ROWCOUNT

While (1 = 1)
Begin
if (@rows = 0)
Begin
Select @isRouteFound = 0, @msg = 'Passed the end of routes. Route Incomplete'
break;
End

if exists (select top 1 * from @routes where EndNode = @EndNode)
Begin
select @isRouteFound = 1, @msg = 'Route Found'
break;
End

if (@activedepth >= isNull(@depth, @activedepth))
Begin
set @msg = 'Depth Reached - Route not found'
break;
End


/*
1. Forget lower depth routes
2. Make sure we dont loop the same route
2.1 Node will either be in the begining of the route or in the mid.
2.2 The node that is at the end the recent node, so we should not check that
3. Insert records with active depth + 1
*/
Insert into @routes
select RouteMap + ' - ' + CAST(b.user2ID as varchar(3)), b.user2ID, @activedepth + 1 from @routes a left join Friendship b on a.EndNode = b.user1ID
where depth = @activedepth and RouteMap not like '%- ' + CAST(b.user2ID as varchar(3)) + ' -%' and RouteMap not like CAST(b.user2ID as varchar(3)) + ' -%'
Union
select RouteMap + ' - ' + CAST(b.user1ID as varchar(3)), b.user1ID, @activedepth + 1 from @routes a left join Friendship b on a.EndNode = b.user2ID
where depth = @activedepth and RouteMap not like '%- ' + CAST(b.user1ID as varchar(3)) + ' -%' and RouteMap not like CAST(b.user1ID as varchar(3)) + ' -%'

select @rows = @@ROWCOUNT, @activedepth = @activedepth + 1

--select *from @routes
End
End

--select * from @routes
--select @isRouteFound Result, @depth Depth

if (@isRouteFound = 1)
select RouteMap, depth, @msg Result from @routes where EndNode = @EndNode
else
select null RouteMap, -1 depth, @msg Result
End