日期:2014-05-18  浏览次数:20499 次

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 code

/*
标题: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
go

select * , 
       dbo.f_pid1(id) [路径(从父到子)] ,
       dbo.f_pid2(id) [路径(从子到父)]
from tb order by id

drop 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
00