SQL与最短路径算法(1)

题目:空间有若干个点，每个点之间的联系都是随机的，现求任意一个点(设为A)到另一任意点(设为Z)之间间隔最少其他点的最佳算法(可用SQL数据库)

约束:在一个点中只可以直接找出和它有直接联系的点

用途:通过朋友列表以最快的速度认识一个认识的人(MM/GG)

比如5的好友列表中有1，30，3

7的好友列表中有9，5，8

10的好友列表中有7，21，30

11的好友列表中有7，5，30

21的好友列表中有7，30，66

30的好友列表中有21，88，99

如果5要和7交朋友，则可通过5-11-7。而5-30-21-7是较长的路径。

各位大虾有什么绝招能在SQL里实现这算法?

--如果全部建立双向关联，可以试试看下面的语句

declare @t table

(

id int,

f_id varchar(20)

)

insert into @t

select 5,'1,7,30,3' union all

select 7,'11,21,9,5,8' union all

select 11,'7,21,30' union all

select 21,'7,11,30,66' union all

select 30,'5,11,21,88,99'

--select * from @t

declare @start int

declare @end int

declare @node int

declare @count int

declare @result varchar(100)

set @count=0

set @start=5

set @end=11

set @result=''

declare @tmp table

(

id int,

f_id varchar(20),

step int

)

insert into @tmp select @start,'',@count

while @end not in (select id from @tmp)

begin

set @count=@count+1

insert into @tmp

select distinct a.id,a.f_id,@count from @t a,@tmp b where charindex(rtrim(b.id),a.f_id)>0 and a.id not in (select id from @tmp)

end

select @result=rtrim(@count)+':'+rtrim(@end)

while @count>1

begin

set @count=@count-1

select top 1 @end=id from @tmp where step=@count and charindex(rtrim(@end),f_id)>0

select @result=rtrim(@count)+':'+rtrim(@end)+'/'+@result

end

select @result='0:'+rtrim(@start)+'/'+@result

select @result

/*

0:5/1:7/2:11

*/

点评：上面的方法的缺点是不能列出所有的路径，只能列出最短路径其中一条

5的列表中没有7，是不是可以认为5不认识7，那么5也不认识11，谈何5-11-7是最短路径？