SQL和最短路径算法

　　SQL和最短路径算法

　　题目:空间有若干个点，每个点之间的联系都是随机的，现求任意一个点(设为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是最短路径？

--按照您说的逻辑，步骤如下

--1.建立查询函数
CREATE FUNCTION dbo.F_RouteSearch
(
@START INT,
@END INT
)
RETURNS VARCHAR(200)
AS
BEGIN
DECLARE @NODE INT
DECLARE @COUNT INT
DECLARE @RESULT VARCHAR(100)
SET @COUNT=0
SET @RESULT=''
DECLARE @TMP TABLE
(
ID INT,
F_ID VARCHAR(20),
STEP INT
)
INSERT INTO @TMP SELECT @START,(SELECT F_ID FROM LIST WHERE ID=@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 List a,@TMP b WHERE CHARINDEX(',' RTRIM(a.ID) ',',',' b.F_ID ',')>0 and a.ID not in (SELECT ID FROM @TMP)
IF @@ROWCOUNT=0
BEGIN
SELECT @RESULT='NO ROUTE FIND'
GOTO RETURNHANDLE
END
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
RETURNHANDLE:
RETURN @RESULT
END
GO

--准备测试数据（和LZ提供数据相同）
insert into list
select 5,'1,30,3' union all
select 7,'9,5,8' union all
select 10,'7,21,30' union all
select 11,'7,5,30' union all
select 21,'7,66,30' union all
select 30,'21,88,99'
go
--测试

select dbo.F_RouteSearch(5,7) --从5开始，到7为止

--结果
/*
0:5→1:30→2:21→3:7
注解
5通过30，21最后找到7，耗费3步完成
5不认识11，因此LZ所说的路径5-11-7不成立
*/

--List表生成脚本

CREATE TABLE [List] (
[id] [int] NULL ,
[f_id] [varchar] (40) COLLATE Chinese_PRC_CI_AS NULL
) ON [PRIMARY]
GO

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有