sqlserver2005中求最短路径

用CTE语句: with.. as (.. )
查询出所有可能的路径,然后选最少行数的.

/*
标题：SQL SERVER 2000中查询指定节点及其所有父节点的函数(字符串形式显示)
作者：爱新觉罗·毓华(十八年风雨,守得冰山雪莲花开)
时间：2010-02-02
地点：新疆乌鲁木齐
*/create table tb(id varchar(3) , pid varchar(3) , name varchar(10))
insert into tb values('001' , null  , '广东省')
insert into tb values('002' , '001' , '广州市')
insert into tb values('003' , '001' , '深圳市')
insert into tb values('004' , '002' , '天河区')
insert into tb values('005' , '003' , '罗湖区')
insert into tb values('006' , '003' , '福田区')
insert into tb values('007' , '003' , '宝安区')
insert into tb values('008' , '007' , '西乡镇')
insert into tb values('009' , '007' , '龙华镇')
insert into tb values('010' , '007' , '松岗镇')
go--查询各节点的父路径函数(从父到子)
create function f_pid1(@id varchar(3)) returns varchar(100)
as
begin
  declare @re_str as varchar(100)
  set @re_str = ''
  select @re_str = name from tb where id = @id
  while exists (select 1 from tb where id = @id and pid is not null)
    begin
      select @id = b.id , @re_str = b.name + ',' + @re_str from tb a , tb b where a.id = @id and a.pid = b.id
    end
  return @re_str
end
go
--查询各节点的父路径函数(从子到父)
create function f_pid2(@id varchar(3)) returns varchar(100)
as
begin
  declare @re_str as varchar(100)
  set @re_str = ''
  select @re_str = name from tb where id = @id
  while exists (select 1 from tb where id = @id and pid is not null)
    begin
      select @id = b.id , @re_str = @re_str + ',' + b.name from tb a , tb b where a.id = @id and a.pid = b.id
    end
  return @re_str
end
goselect * ,
       dbo.f_pid1(id) [路径(从父到子)] ,
       dbo.f_pid2(id) [路径(从子到父)]
from tb order by iddrop function f_pid1 , f_pid2
drop table tb/*
id   pid  name    路径(从父到子)               路径(从子到父)
---- ---- ------  ---------------------------  ----------------------------
001  NULL 广东省  广东省                       广东省
002  001  广州市  广东省,广州市                广州市,广东省
003  001  深圳市  广东省,深圳市                深圳市,广东省
004  002  天河区  广东省,广州市,天河区         天河区,广州市,广东省
005  003  罗湖区  广东省,深圳市,罗湖区         罗湖区,深圳市,广东省
006  003  福田区  广东省,深圳市,福田区         福田区,深圳市,广东省
007  003  宝安区  广东省,深圳市,宝安区         宝安区,深圳市,广东省
008  007  西乡镇  广东省,深圳市,宝安区,西乡镇  西乡镇,宝安区,深圳市,广东省
009  007  龙华镇  广东省,深圳市,宝安区,龙华镇  龙华镇,宝安区,深圳市,广东省
010  007  松岗镇  广东省,深圳市,宝安区,松岗镇  松岗镇,宝安区,深圳市,广东省（所影响的行数为 10 行）
*/SQL code
/*
标题：SQL SERVER 2005中查询指定节点及其所有父节点的方法(字符串形式显示)
作者：爱新觉罗·毓华(十八年风雨,守得冰山雪莲花开)
时间：2010-02-02
地点：新疆乌鲁木齐
*/create table tb(id varchar(3) , pid varchar(3) , name nvarchar(10))
insert into tb values('001' , null  , N'广东省')
insert into tb values('002' , '001' , N'广州市')
insert into tb values('003' , '001' , N'深圳市')
insert into tb values('004' , '002' , N'天河区')
insert into tb values('005' , '003' , N'罗湖区')
insert into tb values('006' , '003' , N'福田区')
insert into tb values('007' , '003' , N'宝安区')
insert into tb values('008' , '007' , N'西乡镇')
insert into tb values('009' , '007' , N'龙华镇')
insert into tb values('010' , '007' , N'松岗镇')
go;with t as
(
    select id , pid = id from tb
    union all
    select t.id , pid = tb.pid from t inner join tb on t.pid = tb.id
)
select id ,
       [路径(从父到子)] = STUFF((SELECT ',' + pid FROM t WHERE id = tb.id order by t.id , t.pid FOR XML PATH('')) , 1 , 1 , ''),
       [路径(从子到父)] = STUFF((SELECT ',' + pid FROM t WHERE id = tb.id FOR XML PATH('')) , 1 , 1 , '')
from tb
group by id
order by id
/*
id   路径(从父到子)   路径(从子到父)
---- ---------------  ---------------
001  001              001
002  001,002          002,001
003  001,003          003,001
004  001,002,004      004,002,001
005  001,003,005      005,003,001
006  001,003,006      006,003,001
007  001,003,007      007,003,001
008  001,003,007,008  008,007,003,001
009  001,003,007,009  009,007,003,001
010  001,003,007,010  010,007,003,001(10 行受影响)
*/
;with t as
(
    select id , name , pid = id , path = cast(name as nvarchar(100)) from tb
    union all
    select t.id , t.name , pid = tb.pid , path = cast(tb.name as nvarchar(100)) from t join tb on tb.id = t.pid
)
select id ,
       name ,
       [路径(从父到子)_1] = pid1,
       [路径(从父到子)_2] = reverse(substring(reverse(path1) , charindex(',' , reverse(path1)) + 1 , len(path1))) ,
       [路径(从子到父)_1] = pid2,
       [路径(从子到父)_2] = substring(path2 , charindex(',' , path2) + 1 , len(path2)) from
(
select id , name ,
       pid1 = STUFF((SELECT ',' + pid FROM t WHERE id = tb.id order by t.id , t.pid FOR XML PATH('')) , 1 , 1 , ''),
       pid2 = STUFF((SELECT ',' + pid FROM t WHERE id = tb.id FOR XML PATH('')) , 1 , 1 , ''),
       path1 = STUFF((SELECT ',' + path FROM t WHERE id = tb.id order by t.id , t.pid FOR XML PATH('')) , 1 , 1 , ''),
       path2 = STUFF((SELECT ',' + path FROM t WHERE id = tb.id FOR XML PATH('')) , 1 , 1 , '')
from tb
group by id , name
) m
order by id
/*
id   name    路径(从父到子)_1  路径(从父到子)_2             路径(从子到父)_1  路径(从子到父)_2
---- ------  ----------------  ---------------------------  ----------------  ---------------------------
001  广东省  001               广东省                       001               广东省
002  广州市  001,002           广东省,广州市                002,001           广州市,广东省
003  深圳市  001,003           广东省,深圳市                003,001           深圳市,广东省
004  天河区  001,002,004       广东省,广州市,天河区         004,002,001       天河区,广州市,广东省
005  罗湖区  001,003,005       广东省,深圳市,罗湖区         005,003,001       罗湖区,深圳市,广东省
006  福田区  001,003,006       广东省,深圳市,福田区         006,003,001       福田区,深圳市,广东省
007  宝安区  001,003,007       广东省,深圳市,宝安区         007,003,001       宝安区,深圳市,广东省
008  西乡镇  001,003,007,008   广东省,深圳市,宝安区,西乡镇  008,007,003,001   西乡镇,宝安区,深圳市,广东省
009  龙华镇  001,003,007,009   广东省,深圳市,宝安区,龙华镇  009,007,003,001   龙华镇,宝安区,深圳市,广东省
010  松岗镇  001,003,007,010   广东省,深圳市,宝安区,松岗镇  010,007,003,001   松岗镇,宝安区,深圳市,广东省(10 行受影响)
*/drop table tb--参考一下实例
--> 生成测试数据表:tb
IF NOT OBJECT_ID('[tb]') IS NULL
DROP TABLE [tb]
GO
CREATE TABLE [tb](GUID INT IDENTITY,[col1] NVARCHAR(10),[col2] NVARCHAR(20))
INSERT [tb]
SELECT N'A','01' UNION ALL
SELECT N'B','01.01' UNION ALL
SELECT N'C','01.01.01' UNION ALL
SELECT N'F','01.01.01.01' UNION ALL
SELECT N'E','01.01.01.02' UNION ALL
SELECT N'D','01.01.01.03' UNION ALL
SELECT N'O','02' UNION ALL
SELECT N'P','02.01' UNION ALL
SELECT N'Q','02.01.01'
GO
--SELECT * FROM [tb]-->SQL查询如下:---另一种方法
;WITH T AS
(
   SELECT *,PATH=CAST([COL1] AS VARCHAR(1000)) FROM TB A
       WHERE NOT EXISTS(
        SELECT 1 FROM TB
     WHERE A.COL2 LIKE COL2+'%'
   AND LEN(A.COL2)>LEN(COL2))
   UNION ALL
   SELECT A.*,CAST(PATH+'-->'+A.COL1 AS VARCHAR(1000))
   FROM TB A
   JOIN T B
        ON A.COL2 LIKE B.COL2+'%'            AND LEN(A.COL2)-3=LEN(B.COL2)
)SELECT * FROM T ORDER BY LEFT(COL2,2)/*GUID        COL1        COL2                  PATH----------- ---------- -------------------- --------------------1           A          01                   A2           B          01.01                A-->B3           C          01.01.01             A-->B-->C4           F          01.01.01.01          A-->B-->C-->F5           E          01.01.01.02          A-->B-->C-->E6           D          01.01.01.03          A-->B-->C-->D7           O          02                   O8           P          02.01                O-->P9           Q          02.01.01             O-->P-->Q
(9 行受影响)*/
;WITH T AS(
    SELECT *,CAST(COL1  AS VARCHAR(1000)) AS PATH
    FROM  TB
    WHERE COL2 NOT LIKE '%.%'
    UNION ALL
    SELECT A.*,CAST(B.PATH+'-->'+A.COL1 AS VARCHAR(1000))
    FROM TB A,T B
    WHERE A.COL2 LIKE B.COL2+'.[01-99][01-99]'
)SELECT * FROM T
ORDER BY LEFT(COL2,2)/*GUID        COL1        COL2                  PATH----------- ---------- -------------------- --------------------1           A          01                   A2           B          01.01                A-->B3           C          01.01.01             A-->B-->C4           F          01.01.01.01          A-->B-->C-->F5           E          01.01.01.02          A-->B-->C-->E6           D          01.01.01.03          A-->B-->C-->D7           O          02                   O8           P          02.01                O-->P9           Q          02.01.01             O-->P-->Q (9 行受影响)*/
参考资料，查询出来后选择最短的

只需要求出经过路径的条数，比如e到h的查询结果为 e h 5。

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

--最短乘车路线查询示例(邹老大的。)
CREATE TABLE T_Line(
ID      nvarchar(10),  --公交线路号
Station nvarchar(10),  --站点名称
Orders  int)           --行车方向(通过它反应每个站的上一个、下一个站)
INSERT T_Line
SELECT N'8路'  ,N'站A',1 UNION ALL
SELECT N'8路'  ,N'站B',2 UNION ALL
SELECT N'8路'  ,N'站C',3 UNION ALL
SELECT N'8路'  ,N'站D',4 UNION ALL
SELECT N'8路'  ,N'站J',5 UNION ALL
SELECT N'8路'  ,N'站L',6 UNION ALL
SELECT N'8路'  ,N'站M',7 UNION ALL
SELECT N'20路' ,N'站G',1 UNION ALL
SELECT N'20路' ,N'站H',2 UNION ALL
SELECT N'20路' ,N'站I',3 UNION ALL
SELECT N'20路' ,N'站J',4 UNION ALL
SELECT N'20路' ,N'站L',5 UNION ALL
SELECT N'20路' ,N'站M',6 UNION ALL
SELECT N'255路',N'站N',1 UNION ALL
SELECT N'255路',N'站O',2 UNION ALL
SELECT N'255路',N'站P',3 UNION ALL
SELECT N'255路',N'站Q',4 UNION ALL
SELECT N'255路',N'站J',5 UNION ALL
SELECT N'255路',N'站D',6 UNION ALL
SELECT N'255路',N'站E',7 UNION ALL
SELECT N'255路',N'站F',8
GO--乘车线路查询存储过程
CREATE PROC p_qry
@Station_Start nvarchar(10),
@Station_Stop  nvarchar(10)
AS
SET NOCOUNT ON
DECLARE @l int
SET @l=0
SELECT ID,Station,
Line=CAST('('+RTRIM(ID)+': '+RTRIM(Station) as nvarchar(4000)),
Orders=Orders,
[Level]=@l
INTO # FROM T_Line
WHERE Station=@Station_Start
WHILE @@ROWCOUNT>0
AND NOT EXISTS(SELECT * FROM # WHERE Station=@Station_Stop)
BEGIN
SET @l=@l+1
INSERT #(Line,ID,Station,Orders,[Level])
SELECT
Line=a.Line+CASE
WHEN a.ID=b.ID THEN N'->'+RTRIM(b.Station)
ELSE N') ∝ ('+RTRIM(b.ID)
+N': '+RTRIM(b.Station) END,
b.ID,b.Station,b.Orders,@l
FROM # a,T_Line b
WHERE a.[Level]=@l-1
AND(a.Station=b.Station AND a.ID<>b.ID
OR a.ID=b.ID AND(
a.Orders=b.Orders+1
OR
a.Orders=b.Orders-1))
AND LEN(a.Line)<4000
AND PATINDEX('%[ >]'+b.Station+'[-)]%',a.Line)=0
END
SELECT N'起点站'=@Station_Start
,N'终点站'=@Station_Stop
,N'乘车线路'=Line+N')'
FROM #
WHERE [Level]=@l
AND Station=@Station_Stop
IF @@ROWCOUNT =0 --如果未有可以到达的线路,则显示处理结果表备查
SELECT * FROM #
GO--调用
EXEC p_qry N'站A',N'站L'
/*--结果
起点站  终点站  乘车线路
---------- ------------ -----------------------------------------------------------
站A    站L    (8路: 站A->站B->站C->站D->站J->站L)
--*/

----创建测试数据表
create table #road
(p1 varchar(10),
p2 varchar(10))
---建立测试数据
insert into #road(p1,p2) values('a', 'g10')
insert into #road(p1,p2) values('a', 'g1')
insert into #road(p1,p2) values('a', 'g2')
insert into #road(p1,p2) values('a', 'g3')
insert into #road(p1,p2) values('a', 'b')
insert into #road(p1,p2) values('a', 'c')
insert into #road(p1,p2) values('b', 'g4')
insert into #road(p1,p2) values('b', 'g7')
insert into #road(p1,p2) values('c', 'g2')
insert into #road(p1,p2) values('c', 'g5')
insert into #road(p1,p2) values('d', 'g1')
insert into #road(p1,p2) values('d', 'g6')
insert into #road(p1,p2) values('d', 'g6')
insert into #road(p1,p2) values('e', 'g3')
insert into #road(p1,p2) values('e', 'g8')
insert into #road(p1,p2) values('h', 'g4')
insert into #road(p1,p2) values('h', 'g9')----select * from #road
---创建路径计算表
create table #path
(start varchar(10),
path_m varchar(10),
c_path varchar(1000),
path_n int
)---drop table #path
----select * from #path
---定义开始和结束路径
declare @start varchar(10)
declare @end varchar(10)select @start = 'a'
select @end = 'h'
---定义路径计算中间值变量
declare @path varchar(100)
select @path = ''
---定义计算步数
declare @step int---创建路径计算表初始数据，正反两遍运算 insert into #path(start,path_m,c_path,path_n)
select @start,p2,@start+'-'+p2,1 from #road
where p1 = @start

insert into #path(start,path_m,c_path,path_n)
select @start,p1,@start+'-'+p1,1 from #road
where p2 = @start
---创建路径集合，判断是否到达终点
select @path = @path + path_m+',' from
(select distinct(path_m) path_m from #path) path_m
---计算步数赋值
select @step = max(path_n) from #path
----select @path
----select @step
---循环计算，直到第一次到达终点，也就是最短路径
while charindex(@end,@path) = 0
begin
----路径计算，正反两遍运算
insert into #path(start,path_m,c_path,path_n)
select @start,#road.p1,#path.c_path+'-'+#road.p1,#path.path_n+1
from #path,#road
where #path.path_m = #road.p2
and #path.path_n = @step

insert into #path(start,path_m,c_path,path_n)
select @start,#road.p2,#path.c_path+'-'+#road.p2,#path.path_n+1
from #path,#road
where #path.path_m = #road.p1
and #path.path_n = @step
---删除原来的计算步骤
delete #path
where path_n = @step
---删除循环回去的路径
delete #path
from
(select path_m,
SUBSTRING(c_path,1,LEN(c_path)-len(path_m)) as c_path_def,c_path
from #path) path_def
where CHARINDEX(path_def.path_m,path_def.c_path_def) <> 0
and path_def.c_path = #path.c_path
----中间路径集合和计算步数重新赋值
select @step = max(path_n) from #path
select @path = ''
select @path = @path + path_m+',' from
(select distinct(path_m) path_m from #path) path_m

----找不到路径，就直接跳出循环
if not exists(select * from #path)
begin
break
end

end
----计算结束，删除不是到达终点的数据
delete #path
where path_m <> @end
---显示计算结果
select * from #path---计算结果
---a h a-b-g4-h 3

调试易

sqlserver2005中求最短路径

解决方案 »