SQL Server在SQL Server实现最缺路径的寻

 

开始

 

眼看是去年底题材了,今天在整理邮件的时光才发觉这题目,感觉顶有意思的,特记录下来。

每当表RelationGraph中,有三独字段(ID,Node,RelatedNode),其中Node和RelatedNode两个字段描述两单节点的连天关系;现在求,找来由节点”p”至节点”j”,最短路径(即由此的节点最少)。

SQL Server 1

图1.

 

 

解析

 

以能还好的讲述表RelationGraph中字段Node和
RelatedNode的涉,我以此间特别利用一个图来讲述,如图2.

SQL Server 2

图2.

 

当图2,可清的观望各个节点直接如何不断,也足以了解的收看节点”p”至节点”j”的之几乎种或路径。

SQL Server 3

于上面可以看看第2种植或路径,经过的节点最少。

为缓解起来之题材,我参考了点滴种方法,

第1方法是,

参照单源最缺少路径算法:Dijkstra(迪杰斯特拉)算法,主要特色是为自始点为主导往外少有扩展,直到扩展至终极为止。

SQL Server 4

图3.

第2方法是,

针对第1种植办法的改善,就是应用多源点方法,这里虽是坐节点”p”和节点”j”为主干向外围扩展,直到片到家他切点,如图4.

SQL Server 5

图4.

 

 

实现

当对接下去,我虽讲述在SQL
Server中,如何促成。当然我这边用的前面说之第2栽方式,以”P”和”J”为始点像中心外少有扩展。

 (注:以下的下边论是以SQL Server
2012测试通过,也可运行在SQL Server 2008/2008R2及

此提供有表RelactionGraph的create& Insert数据的脚本:

use TestDB    

go

 

if object_id(‘RelactionGraph’) Is not null drop table RelactionGraph

create table RelactionGraph(ID int identity,Item nvarchar(50),RelactionItem nvarchar(20),constraint PK_RelactionGraph primary key(ID))

go

create nonclustered index IX_RelactionGraph_Item on RelactionGraph(Item) include(RelactionItem)

create nonclustered index IX_RelactionGraph_RelactionItem on RelactionGraph(RelactionItem) include(Item)

go

 

insert into RelactionGraph (Item, RelactionItem ) values

    (‘a’,’b’),(‘a’,’c’),(‘a’,’d’),(‘a’,’e’),

    (‘b’,’f’),(‘b’,’g’),(‘b’,’h’),

    (‘c’,’i’),(‘c’,’j’),

    (‘f’,’k’),(‘f’,’l’),

    (‘k’,’o’),(‘k’,’p’),

    (‘o’,’i’),(‘o’,’l’)

 

go

编写一个存储过程up_GetPath

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来说,它们两者相互为参照对象,进行向外找用。

下面是储存过程的执行:

use TestDB

go

exec dbo.up_GetPath

        @Node = ‘p’,

@RelatedNode = ‘j’

 

go

 

SQL Server 6

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

 

扩展

前面的例证,可扩大至市之公交路线,提供个别个站点,搜索经过及时点儿单站点最少站点公交路线;可以扩展及社区的人际关系的寻,如一个人口跟其余一个人口思念认识,那么他们直接而由此多少个人才好。除了人同丁直接发生直接的情侣、亲戚关系,还足以经过人数跟物有关联找到人跟人关系,如几只作家经过出版一个按照,那么就算认证这几个人好通过某同本书的作者列表中找到她们在并出版图书的涉及,这吗找两个人认路线提供参考。这题目或者会见要命非常复杂,但好这样的扩充。

 

小结

 

这边只是找点儿只节点的有途径中,节点数最少的路线,在实质上的应用被,可能会见遇上比这里又扑朔迷离的图景。在其它的环境或现象可能会见包含长度,时间,多节点,多作用域等局部信息。无论如何,一般还如参考一些规律,算法来落实。

 

相关文章