注册 登录
编程论坛 → SQL Server论坛

问站Ａ－站Ｌ最短乘车路线(SQL问题)

accpfriend 发布于 2007-01-10 12:07， 1821 次点击

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
select * from T_Line

问Ａ　　－　　Ｌ最短乘车路线
我自己的题看了半天都还不会动手，请网上的高手帮助

/*--例如
起点站 终点站 乘车线路
---------- ------------ -----------------------------------------------------------
站A 站L (8路: 站A->站B->站C->站D->站J->站L)
--*/

15 回复
#2
棉花糖ONE2007-01-10 12:17
不会，帮你顶
#3
accpfriend2007-01-10 16:03

没办法,请教了别人才做出来,还是不懂,给大家看看吧

--乘车线路查询存储过程
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'
#4
棉花糖ONE2007-01-10 16:19

csdn上拿的吧
#5
accpfriend2007-01-10 16:22
是的一个高手教我的
#6
accpfriend2007-01-10 16:22
但还是不明白
#7
棉花糖ONE2007-01-10 16:24
这代码是邹老大写的,有时间再看吧,太难了点
#8
chenxkfox2007-01-10 21:39

好帖子！看不懂！
顶一下，请高手解释！
#9
Kendy1234562007-01-11 11:20
以下是引用accpfriend在2007-1-10 16:03:13的发言：

没办法,请教了别人才做出来,还是不懂,给大家看看吧

--乘车线路查询存储过程
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)

当同时满足2个条件时 1. 找到了下一个可访问的站点(rowcount>0) 2.还没有达到给定的终点 (not exist ...) 循环下面的代码
******

BEGIN
SET @l=@l+1 (当前访问层次+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

把符合下面条件之一(or)的的数据插入临时表
1. a.Station=b.Station AND a.ID<>b.ID 同站换公交车了
2. a.ID=b.ID AND( 没有换车
a.Orders=b.Orders+1 上行一站
OR
a.Orders=b.Orders-1)) 下行一站

AND PATINDEX('%[ >]'+b.Station+'[-)]%',a.Line)=0 同一车站不许访问2次

****

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'

[此贴子已经被作者于2007-1-11 11:45:41编辑过]
#10
Kendy1234562007-01-11 11:28

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

exec p_qry 'C','P'



-------------------
Initial temp table:

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 C (8: C 3 0


-----------------------------------------
Loop Level:1

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 B (8: C->B 2 1
8 D (8: C->D 4 1
8 C (8: C 3 0


-----------------------------------------
Loop Level:2

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 B (8: C->B 2 1
8 D (8: C->D 4 1
8 A (8: C->B->A 1 2
8 J (8: C->D->J 5 2
255 D (8: C->D) ∝ (255: D 6 2
8 C (8: C 3 0


-----------------------------------------
Loop Level:3

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 B (8: C->B 2 1
8 D (8: C->D 4 1
8 A (8: C->B->A 1 2
8 J (8: C->D->J 5 2
255 D (8: C->D) ∝ (255: D 6 2
8 L (8: C->D->J->L 6 3
20 J (8: C->D->J) ∝ (20: J 4 3
255 J (8: C->D->J) ∝ (255: J 5 3
255 J (8: C->D) ∝ (255: D->J 5 3
255 E (8: C->D) ∝ (255: D->E 7 3
8 C (8: C 3 0


-----------------------------------------
Loop Level:4

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 B (8: C->B 2 1
8 D (8: C->D 4 1
8 A (8: C->B->A 1 2
8 J (8: C->D->J 5 2
255 D (8: C->D) ∝ (255: D 6 2
8 L (8: C->D->J->L 6 3
20 J (8: C->D->J) ∝ (20: J 4 3
255 J (8: C->D->J) ∝ (255: J 5 3
255 J (8: C->D) ∝ (255: D->J 5 3
255 E (8: C->D) ∝ (255: D->E 7 3
8 J (8: C->D) ∝ (255: D->J) ∝ (8: J 5 4
8 M (8: C->D->J->L->M 7 4
20 I (8: C->D->J) ∝ (20: J->I 3 4
20 J (8: C->D) ∝ (255: D->J) ∝ (20: J 4 4
20 L (8: C->D->J->L) ∝ (20: L 5 4
20 L (8: C->D->J) ∝ (20: J->L 5 4
255 Q (8: C->D->J) ∝ (255: J->Q 4 4
255 Q (8: C->D) ∝ (255: D->J->Q 4 4
255 F (8: C->D) ∝ (255: D->E->F 8 4
8 C (8: C 3 0


-----------------------------------------
Loop Level:5

ID Station Line Orders Level
---------- ---------- ---------------------------------------------------------------------------------------------------- ----------- -----------
8 B (8: C->B 2 1
8 D (8: C->D 4 1
8 A (8: C->B->A 1 2
8 J (8: C->D->J 5 2
255 D (8: C->D) ∝ (255: D 6 2
8 L (8: C->D->J->L 6 3
20 J (8: C->D->J) ∝ (20: J 4 3
255 J (8: C->D->J) ∝ (255: J 5 3
255 J (8: C->D) ∝ (255: D->J 5 3
255 E (8: C->D) ∝ (255: D->E 7 3
8 J (8: C->D) ∝ (255: D->J) ∝ (8: J 5 4
8 M (8: C->D->J->L->M 7 4
20 I (8: C->D->J) ∝ (20: J->I 3 4
20 J (8: C->D) ∝ (255: D->J) ∝ (20: J 4 4
20 L (8: C->D->J->L) ∝ (20: L 5 4
20 L (8: C->D->J) ∝ (20: J->L 5 4
255 Q (8: C->D->J) ∝ (255: J->Q 4 4
255 Q (8: C->D) ∝ (255: D->J->Q 4 4
255 F (8: C->D) ∝ (255: D->E->F 8 4
8 L (8: C->D) ∝ (255: D->J) ∝ (8: J->L 6 5
8 L (8: C->D->J) ∝ (20: J->L) ∝ (8: L 6 5
20 H (8: C->D->J) ∝ (20: J->I->H 2 5
20 I (8: C->D) ∝ (255: D->J) ∝ (20: J->I 3 5
20 L (8: C->D) ∝ (255: D->J) ∝ (20: J->L 5 5
20 M (8: C->D->J->L->M) ∝ (20: M 6 5
20 M (8: C->D->J->L) ∝ (20: L->M 6 5
20 M (8: C->D->J) ∝ (20: J->L->M 6 5
255 P (8: C->D->J) ∝ (255: J->Q->P 3 5
255 P (8: C->D) ∝ (255: D->J->Q->P 3 5
8 C (8: C 3 0

start p end p line
---------- ---------- -----------------------------------------------------------------------------------------------------
C P (8: C->D->J) ∝ (255: J->Q->P)
C P (8: C->D) ∝ (255: D->J->Q->P)

[此贴子已经被作者于2007-1-11 11:33:25编辑过]
#11
accpfriend2007-01-11 11:59
呵呵,强人还是很多呀,我的算法没学好,看了下,还是一头雾
#12
accpfriend2007-01-11 12:16

站A 站G 站N

站B H站

站c 站I

站D 站J

站L 站M

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

大哥，我的理解 是不是Orders相同的 与前一个节点是一样的路程，
能否用图标志下，
#13
Kendy1234562007-01-11 12:18

这个算法不复杂啊

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

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

刚刚又看了看这贴 发现一个问题
这段代码在计算路径的时候 把换乘直接当做一站来处理了 也就是说 从 (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
#15
Kendy1234562007-01-15 11:19

稍微扩展一下 如果要求列出所有可能的路线和途经的车站数
那么只要去掉循环时候的 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编辑过]
#16
防毒面具2007-05-16 17:07
不错 原来SQL也可以求最短路径
1
©2025, BC-CN.NET
电脑版