SQL Server实现短路径的搜索算法

　　你可以根据需要来，赋予@Node 和 @RelatedNode不同的值。

    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) AsRelationGraphPath，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 AndLevel=@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 AndLevel=@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) AsRelationGraphPath，Convert(smallint，1) As PathLevel
    From #1 a where exists(select 1 from #2where 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) AsRelationGraphPath，Convert(smallint，1) As PathLevel
    From #2 a where exists(select 1 from #1where 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 AsRelationGraphPath，a.PathLevel+b.PathLevel -1
    As StopCount，rank() over(order bya.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

　　扩展：

　　前面的例子，可扩展至城市的公交路线，提供两个站点，搜索经过这两个站点少站点公交路线；可以扩展至社区的人际关系的搜索，如一个人与另一个人想认识，那么他们直接要经过多少个人才可以。除了人与人直接有直接的朋友、亲戚关联，还可以通过人与物有关联找到人与人关联，如几个作家通过出版一个本，那么说明这几个人可以通过某一本书的作者列表中找到他们存在共同出版书籍的关联，这为搜索两个人认识路径提供参考。这问题可能会非常大复杂，但可以这样的扩展。

　　小结：

　　这里只是找两个节点的所有路径中，节点数少的路径，在实际的应用中，可能会碰到比这里更复杂的情况。在其他的环境或场景可能会带有长度，时间，多节点，多作用域等一些信息。无论如何，一般都要参考一些原理，算法来实现。