首页    新闻    下载    文档    论坛     最新漏洞    黑客教程    数据库    搜索    小榕软件实验室怀旧版    星际争霸WEB版    最新IP准确查询   
名称: 密码:      忘记密码  马上注册
数据库 :: 数据库

SQL与最短路径算法


http://www.gipsky.com/
题目:空间有若干个点,每个点之间的联系都是随机的,现求任意一个点(设为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是最短路径?
<< SA弱口令带来的安全隐患 存储过程:轻松过滤SQL Server连接 >>
评分
10987654321
API:
gipsky.com& 安信网络
网友个人意见,不代表本站立场。对于发言内容,由发表者自负责任。

系统导航

 

Copyright © 2001-2010 安信网络. All Rights Reserved
京ICP备05056747号