在SQL Server中实现最短路径搜索的解决方法

use TestDB     

use TestDB 
go 
--Procedure: 
if object_id('up_GetPath') Is not null 
    Drop proc up_GetPath 
go 
create proc up_GetPath 
( 
    @Node nvarchar(50), 
    @RelatedNode nvarchar(50) 
) 
As 
set nocount on 

declare 
    @level smallint =1, --当前搜索的深度 
    @MaxLevel smallint=100, --最大可搜索深度 
    @Node_WhileFlag bit=1, --以@Node作为中心进行搜索时候，作为能否循环搜索的标记 
    @RelatedNode_WhileFlag bit=1 --以@RelatedNode作为中心进行搜索时候，作为能否循环搜索的标记 

--如果直接找到两个Node存在直接关系就直接返回 
if Exists(select 1 from RelationGraph where (Node=@Node And RelatedNode=@RelatedNode) or (Node=@RelatedNode And RelatedNode=@Node) ) or @Node=@RelatedNode 
begin 
    select convert(nvarchar(2000),@Node + ' --> '+ @RelatedNode) As RelationGraphPath,convert(smallint,0) As StopCount 
    return 
end 

-- 

if object_id('tempdb..#1') Is not null Drop Table #1 --临时表#1，存储的是以@Node作为中心向外扩展的各节点数据 
if object_id('tempdb..#2') Is not null Drop Table #2 --临时表#2，存储的是以@RelatedNode作为中心向外扩展的各节点数据 

create table #1( 
    Node nvarchar(50),--相对源点 
    RelatedNode nvarchar(50), --相对目标 
    Level smallint --深度 
    ) 

create table #2(Node nvarchar(50),RelatedNode nvarchar(50),Level smallint) 

insert into #1 ( Node, RelatedNode, Level ) 
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@Node union --正向：以@Node作为源查询 
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @Node --反向：以@Node作为目标进行查询 
set @Node_WhileFlag=sign(@@rowcount) 

insert into #2 ( Node, RelatedNode, Level ) 
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@RelatedNode union --正向：以@RelatedNode作为源查询 
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @RelatedNode --反向：以@RelatedNode作为目标进行查询 
set @RelatedNode_WhileFlag=sign(@@rowcount) 

--如果在表RelationGraph中找不到@Node 或 @RelatedNode 数据，就直接跳过后面的While过程 
if not exists(select 1 from #1) or not exists(select 1 from #2) 
begin 
    goto While_Out 
end 

 
while not exists(select 1 from #1 a inner join #2 b on b.RelatedNode=a.RelatedNode) --判断是否出现切点 
     and (@Node_WhileFlag|@RelatedNode_WhileFlag)>0 --判断是否能搜索 
     And @level<@MaxLevel --控制深度 
begin 
    if @Node_WhileFlag >0 
    begin     
        insert into #1 ( Node, RelatedNode, Level ) 
            --正向 
            select a.Node,a.RelatedNode,@level+1 
                From RelationGraph a 
                where exists(select 1 from #1 where RelatedNode=a.Node And Level=@level) And 
                    Not exists(select 1 from #1 where Node=a.Node)             
            union 
            --反向 
            select a.RelatedNode,a.Node,@level+1 
                From RelationGraph a 
                where exists(select 1 from #1 where RelatedNode=a.RelatedNode And Level=@level) And 
                    Not exists(select 1 from #1 where Node=a.RelatedNode) 

        set @Node_WhileFlag=sign(@@rowcount) 

    end 

     
    if @RelatedNode_WhileFlag >0 
    begin         
        insert into #2 ( Node, RelatedNode, Level ) 
            --正向 
            select a.Node,a.RelatedNode,@level+1 
                From RelationGraph a 
                where exists(select 1 from #2 where RelatedNode=a.Node And Level=@level) And 
                    Not exists(select 1 from #2 where Node=a.Node) 
            union 
            --反向 
            select a.RelatedNode,a.Node,@level+1 
                From RelationGraph a 
                where exists(select 1 from #2 where RelatedNode=a.RelatedNode And Level=@level) And 
                    Not exists(select 1 from #2 where Node=a.RelatedNode) 
        set @RelatedNode_WhileFlag=sign(@@rowcount) 
    end 

    select @level+=1 
end 

While_Out: 

--下面是构造返回的结果路径 
if object_id('tempdb..#Path1') Is not null Drop Table #Path1 
if object_id('tempdb..#Path2') Is not null Drop Table #Path2 

;with cte_path1 As 
( 
select a.Node,a.RelatedNode,Level,convert(nvarchar(2000),a.Node+' -> '+a.RelatedNode) As RelationGraphPath,Convert(smallint,1) As PathLevel From #1 a where exists(select 1 from #2 where RelatedNode=a.RelatedNode) 
union all 
select b.Node,a.RelatedNode,b.Level,convert(nvarchar(2000),b.Node+' -> '+a.RelationGraphPath) As RelationGraphPath ,Convert(smallint,a.PathLevel+1) As PathLevel 
    from cte_path1 a 
        inner join #1 b on b.RelatedNode=a.Node 
            and b.Level=a.Level-1 
) 
select * Into #Path1 from cte_path1 

;with cte_path2 As 
( 
select a.Node,a.RelatedNode,Level,convert(nvarchar(2000),a.Node) As RelationGraphPath,Convert(smallint,1) As PathLevel From #2 a where exists(select 1 from #1 where RelatedNode=a.RelatedNode) 
union all 
select b.Node,a.RelatedNode,b.Level,convert(nvarchar(2000),a.RelationGraphPath+' -> '+b.Node) As RelationGraphPath ,Convert(smallint,a.PathLevel+1) 
    from cte_path2 a 
        inner join #2 b on b.RelatedNode=a.Node 
            and b.Level=a.Level-1 
) 
select * Into #Path2 from cte_path2 

;with cte_result As 
( 
select a.RelationGraphPath+' -> '+b.RelationGraphPath As RelationGraphPath,a.PathLevel+b.PathLevel -1 As StopCount,rank() over(order by a.PathLevel+b.PathLevel) As Result_row 
    From #Path1 a 
        inner join #Path2 b on b.RelatedNode=a.RelatedNode 
            and b.Level=1 
    where a.Level=1 
)     
select distinct RelationGraphPath,StopCount From cte_result where Result_row=1 
go

下面是存储过程的执行：

use TestDB 

go

exec dbo.up_GetPath

        @Node = 'p',

@RelatedNode = 'j'

go