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

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

上面的存储过程，主要分为两大部分，第1部分是实现如何搜索，第2部分实现如何构造返回结果。其中第1部分的代码根据前面的方法2，通过@Node 和 @RelatedNode 两个节点向外层搜索，每次搜索返回的节点都保存至临时表#1和#2，再判断临时表#1和#2有没有出现切点，如果出现就说明已找到最短的路径（经过多节点数最少），否则就继续循环搜索，直到循环至最大的搜索深度（@MaxLevel smallint=100）或找到切点。要是到100层都没搜索到切点，将放弃搜索。这里使用最大可搜索深度@MaxLevel，目的是控制由于数据量大可能会导致性能差，因为在这里数据量与搜索性能成反比。代码中还说到一个正向和反向搜索，主要是相对Node 和 RelatedNode来说，它们两者互为参照对象，进行向外搜索使用。

下面是存储过程的执行：