在SQL Server中完成最短途徑搜刮的處理辦法。本站提示廣大學習愛好者：（在SQL Server中完成最短途徑搜刮的處理辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是在SQL Server中完成最短途徑搜刮的處理辦法正文
開端
這是客歲的成績了，明天在整頓郵件的時刻才發明這個成績，感到頂成心思的，特記載上去。
在表RelationGraph中，有三個字段（ID,Node,RelatedNode）,個中Node和RelatedNode兩個字段描寫兩個節點的銜接關系；如今請求，找出從節點"p"至節點"j"，最短途徑（即經由的節點起碼）。
圖1.
解析：
了可以或許更好的描寫表RelationGraph中字段Node和 RelatedNode的關系，我在這裡特地應用一個圖形來描寫，
如圖2.
圖2.
在圖2，可清楚的看出各個節點直接若何相連，也能夠清晰的看出節點"p"至節點"j"的的幾種能夠途徑。
從下面可以看出第2種能夠途徑，經由的節點起碼。
為懂得決開端的成績，我參考了兩種辦法，
第1辦法是，
參考單源最短途徑算法：Dijkstra(迪傑斯特拉)算法，重要特色是以肇端點為中間向外層層擴大，直到擴大到起點為止。
圖3.
第2辦法是，
針對第1種辦法的改良，就是采取多源點辦法，這裡就是以節點"p"和節點"j"為中間向外層擴大，直到兩圓外切點，如圖4. ：
圖4.
完成：
在接上去，我就描寫在SQL Server中，若何完成。固然我這裡采取的後面說的第2種辦法，以"P"和"J"為始點像中間外層層擴大。
這裡供給有表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
你可以依據須要來，付與@Node 和 @RelatedNode分歧的值。
拓展：
後面的例子，可擴大至城市的公交道路，供給兩個站點，搜刮經由這兩個站點起碼站點公交道路；可以擴大至社區的人際關系的搜刮，如一小我與另外一小我想熟悉，那末他們直接要經由若干小我才可以。除人與人直接有直接的同伙、親戚聯系關系，還可以經由過程人與物有聯系關系找到人與人聯系關系，如幾個作家經由過程出書一個本，那末就解釋這幾小我可以經由過程某一本書的作者列表中找到他們存在配合出書書本的聯系關系，這為搜刮兩小我熟悉途徑供給參考。這成績能夠會異常年夜龐雜，但可以如許的擴大。
小結：
這裡只是找兩個節點的一切途徑中，節點數起碼的途徑，在現實的運用中，能夠會碰著比這裡更龐雜的情形。在其他的情況或場景能夠會帶有長度，時光，多節點，多感化域等一些信息。不管若何，普通都要參考一些道理，算法來完成。
