sqlserver2005中求最短路径
数据库中数据的网络图如上
table中有两个字段分别为p1,p2，数据如下
p1----p2
'a', 'g10'
'a', 'g1'
'a', 'g2'
'a', 'g3'
'a', 'b'
'a', 'c'
'b', 'g4'
'b', 'g7'
'c', 'g5'
'd', 'g1'
'd', 'g6'
'e', 'g3'
'e', 'g8'
需要求a到b，a到c, a到d, a到e，a到h，b到c，b到d，b到e，b到h，c到d，c到e，c到h，d到e，d到h，e到h的最短路径，两点之间算作1。
请哪位高手帮帮忙，用什么思想或者代码能求，最好能用sql语句就直接求出来，也可以用代码求。希望能有详细点的注释。
[解决办法]
/*标题：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)asbegin 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_strendgo--查询各节点的父路径函数(从子到父)create function f_pid2(@id varchar(3)) returns varchar(100)asbegin 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_strendgoselect * , dbo.f_pid1(id) [路径(从父到子)] , dbo.f_pid2(id) [路径(从子到父)]from tb order by iddrop function f_pid1 , f_pid2drop 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 tbgroup by idorder by id/*id 路径(从父到子) 路径(从子到父)---- --------------- ---------------001 001 001002 001,002 002,001003 001,003 003,001004 001,002,004 004,002,001005 001,003,005 005,003,001006 001,003,006 006,003,001007 001,003,007 007,003,001008 001,003,007,008 008,007,003,001009 001,003,007,009 009,007,003,001010 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 tbgroup by id , name) morder 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--参考一下实例--> 生成测试数据表:tbIF NOT OBJECT_ID('[tb]') IS NULL DROP TABLE [tb]GOCREATE TABLE [tb](GUID INT IDENTITY,[col1] NVARCHAR(10),[col2] NVARCHAR(20))INSERT [tb]SELECT N'A','01' UNION ALLSELECT N'B','01.01' UNION ALLSELECT N'C','01.01.01' UNION ALLSELECT N'F','01.01.01.01' UNION ALLSELECT N'E','01.01.01.02' UNION ALLSELECT N'D','01.01.01.03' UNION ALLSELECT N'O','02' UNION ALLSELECT N'P','02.01' UNION ALLSELECT 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 行受影响)*/参考资料，查询出来后选择最短的
[解决办法]
--最短乘车路线查询示例(邹老大的。)CREATE TABLE T_Line(ID nvarchar(10), --公交线路号Station nvarchar(10), --站点名称Orders int) --行车方向(通过它反应每个站的上一个、下一个站)INSERT T_Line SELECT N'8路' ,N'站A',1 UNION ALLSELECT N'8路' ,N'站B',2 UNION ALLSELECT N'8路' ,N'站C',3 UNION ALLSELECT N'8路' ,N'站D',4 UNION ALLSELECT N'8路' ,N'站J',5 UNION ALLSELECT N'8路' ,N'站L',6 UNION ALLSELECT N'8路' ,N'站M',7 UNION ALLSELECT N'20路' ,N'站G',1 UNION ALLSELECT N'20路' ,N'站H',2 UNION ALLSELECT N'20路' ,N'站I',3 UNION ALLSELECT N'20路' ,N'站J',4 UNION ALLSELECT N'20路' ,N'站L',5 UNION ALLSELECT N'20路' ,N'站M',6 UNION ALLSELECT N'255路',N'站N',1 UNION ALLSELECT N'255路',N'站O',2 UNION ALLSELECT N'255路',N'站P',3 UNION ALLSELECT N'255路',N'站Q',4 UNION ALLSELECT N'255路',N'站J',5 UNION ALLSELECT N'255路',N'站D',6 UNION ALLSELECT N'255路',N'站E',7 UNION ALLSELECT N'255路',N'站F',8GO--乘车线路查询存储过程CREATE PROC p_qry@Station_Start nvarchar(10),@Station_Stop nvarchar(10)ASSET NOCOUNT ONDECLARE @l intSET @l=0SELECT ID,Station, Line=CAST('('+RTRIM(ID)+': '+RTRIM(Station) as nvarchar(4000)), Orders=Orders, [Level]=@lINTO # FROM T_LineWHERE Station=@Station_StartWHILE @@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)=0ENDSELECT N'起点站'=@Station_Start ,N'终点站'=@Station_Stop ,N'乘车线路'=Line+N')' FROM # WHERE [Level]=@l AND Station=@Station_StopIF @@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) = 0begin ----路径计算，正反两遍运算 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