问站Ａ－站Ｌ最短乘车路线(SQL问题) - SQL Server论坛

问题点数：0 回复次数：15

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

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)
--*/

搜索更多相关主题的帖子: SQL　UNION　SELECT　ALL　公交线路　

第 2 楼

得分:0

不会，帮你顶

26403021 sql群博客 blog./user15/81152/index.shtml

第 3 楼

得分:0

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

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

得分:0

csdn上拿的吧

26403021 sql群博客 blog./user15/81152/index.shtml

第 5 楼

得分:0

是的一个高手教我的

第 6 楼

得分:0

但还是不明白

第 7 楼

得分:0

这代码是邹老大写的,有时间再看吧,太难了点

26403021 sql群博客 blog./user15/81152/index.shtml

第 8 楼

得分:0

好帖子！看不懂！
顶一下，请高手解释！

,SQL SERVER 群号：17280478

第 9 楼

得分:0

以下是引用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 楼

得分:0

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

exec p_qry 'C','P'

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

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

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

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

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

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

-----------------------------------------
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编辑过]