站A 站G 站N

站B H站

站c 站I

站D 站J

站L 站M

这实际是个遍历的算法 从起点开始遍历所有可能的分支 直到第一次到达终点
我把这个sp稍微改造了一下 增加了中间输出 大家可以看看临时表中的数据每一次循环的变化:

大哥，我的理解 是不是Orders相同的 与前一个节点是一样的路程，
能否用图标志下，

这个算法不复杂啊

从起点开始(节点=start position)
step 1.找到本轮节点所有可能访问到的下一节点,包括本站可换乘的公交车的上一站,下一站和本站的下一站(不许坐回头车 就是以前已经到过的站就不在结果内了)
step 2.上一步找到的站点数大于0吗? (否 表示从起点开始经过的所有可换乘的公交车都走到底了 不能再开了 也就是遍历结束了)
step 3.对于1找到的所有下一站 判断 这些站里面包含我们要找的终点吗? A 是 (遍历结束了) B 不是 (回到step 1, 所有找到的站点都作为起始节点)

注意Sp的处理和vb的处理不同之处在于每一步都是同时对当前遍历层次的所有车站操作的 相对于节省了一层循环的嵌套

刚刚又看了看这贴 发现一个问题
这段代码在计算路径的时候 把换乘直接当做一站来处理了 也就是说 从 (8: C->D) ∝ (255: D 认为是开了2站 实际上应该是只有一站 因为公交车一共就开了一站嘛. 在求最少站点问题的时候 这种逻辑可能会给出多余的答案.
假如 8路是A B C D E的站 255是 B D E F 的站 那么从A到E 存储过程会列出2种路线
8: A-B-C-D-E 是五站 8: A-B,255:B-D-E. 后者其实是4站 但是 也被认为是5站. 如果按照要求 就应该只返回第二条路线才正确

如果这样考虑的话 代码就要改造了

CREATE PROC p_qry
@Station_Start nvarchar(10),
@Station_Stop nvarchar(10)
AS
SET NOCOUNT ON
DECLARE @l int,@RowCnt 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

SET @RowCnt = @@RowCount

WHILE @RowCnt>0
AND NOT EXISTS(SELECT * FROM # WHERE Station=@Station_Stop)
BEGIN
SET @l=@l+1
SET @RowCnt = 0
INSERT #(Line,ID,Station,Orders,[Level])
SELECT
Line=a.Line+ N'->'+RTRIM(b.Station),
b.ID,b.Station,b.Orders,@l
FROM # a,T_Line b
WHERE a.[Level]=@l-1
AND(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

SET @RowCnt = @RowCnt + @@RowCount
INSERT #(Line,ID,Station,Orders,[Level])
SELECT
Line=a.Line+ N') ∝ ('+RTRIM(b.ID)
+N': '+RTRIM(b.Station) ,
b.ID,b.Station,b.Orders,@l
FROM (Select t.id,t.station,t.orders,line from T_Line t, # v where v.station = t.Station AND v.ID<>t.ID and v.level = @l-1 ) a,T_Line b
WHERE 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

SET @RowCnt = @RowCnt + @@RowCount
END

SELECT N'start p'=@Station_Start
,N'end p'=@Station_Stop
,N'line'=Line+N')'
,level
FROM #
WHERE [Level]=@l
AND Station=@Station_Stop
IF @@ROWCOUNT =0
SELECT * FROM #
GO

稍微扩展一下 如果要求列出所有可能的路线和途经的车站数
那么只要去掉循环时候的 NOT EXIST 条件,最后显示的时候去掉 level = @l 条件就可以了

代码如下

create PROC p_qry
@Station_Start nvarchar(10),
@Station_Stop nvarchar(10)
AS

DECLARE @l int,@RowCnt 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

SET @RowCnt = @@RowCount

WHILE @RowCnt>0
BEGIN
SET @l=@l+1
SET @RowCnt = 0
INSERT #(Line,ID,Station,Orders,[Level])
SELECT
Line=a.Line+ N'->'+RTRIM(b.Station),
b.ID,b.Station,b.Orders,@l
FROM # a,T_Line b
WHERE a.[Level]=@l-1
AND(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

SET @RowCnt = @RowCnt + @@RowCount
INSERT #(Line,ID,Station,Orders,[Level])
SELECT
Line=a.Line+ N') ∝ ('+RTRIM(b.ID)
+N': '+RTRIM(b.Station) ,
b.ID,b.Station,b.Orders,@l
FROM (Select t.id,t.station,t.orders,line from T_Line t, # v where v.station = t.Station AND v.ID<>t.ID and v.level = @l-1 ) a,T_Line b
WHERE 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

SET @RowCnt = @RowCnt + @@RowCount
END

SELECT N'start p'=@Station_Start
,N'end p'=@Station_Stop
,N'line'=Line+N')'
,level
FROM #
WHERE Station=@Station_Stop
IF @@RowCount =0
SELECT * FROM #
GO

[此贴子已经被作者于2007-1-15 11:21:18编辑过]