多条路线的查找有关问题

多条路线的查找问题
表t1有两列 f1 表示站点编号 f2 表示与它相通的站点编号
列f1   列f2
AB
AF
AG
BC
BG
BH
BA
CB
CH
CI
CD
DC
DI
DJ
EJ
ED
FA
FG
GA
GB
GH
GF
HG
HB
HC
HI
IH
IC
ID
IF
FI
FD
FE

现在如果我想查找 从A到 I怎么走路线，，应该会有多条路线， 想通过sql来实现查找方式，不知道可有好的方法。
[最优解释]

--> 测试数据：[TB]
if object_id('[TB]') is not null drop table [TB]
GO
create table [TB]([f1] varchar(1),[f2] varchar(1))
insert [TB]
select 'A','B' union all
select 'A','F' union all
select 'A','G' union all
select 'B','C' union all
select 'B','G' union all
select 'B','H' union all
select 'B','A' union all
select 'C','B' union all
select 'C','H' union all
select 'C','I' union all
select 'C','D' union all
select 'D','C' union all
select 'D','I' union all
select 'D','J' union all
select 'E','J' union all
select 'E','D' union all
select 'F','A' union all
select 'F','G' union all
select 'G','A' union all
select 'G','B' union all
select 'G','H' union all
select 'G','F' union all
select 'H','G' union all
select 'H','B' union all
select 'H','C' union all
select 'H','I' union all
select 'I','H' union all
select 'I','C' union all
select 'I','D' union all
select 'I','F' union all
select 'F','I' union all
select 'F','D' union all
select 'F','E'

DECLARE @start VARCHAR(10),@end VARCHAR(10)
SET @start='A'
SET @end='I'

IF OBJECT_ID('tempdb..#temp') IS NOT NULL
     DROP TABLE #temp

CREATE TABLE #temp(
way VARCHAR(MAX),
f1 VARCHAR(10),
f2 VARCHAR(10),
flag int)


INSERT INTO #temp
SELECT ','+f1+','+f2,f1,f2,0 FROM tb WHERE f1=@start

WHILE (SELECT COUNT(1) FROM #temp WHERE flag=0)>0
BEGIN
DECLARE @i VARCHAR(10),@j VARCHAR(MAX)
SELECT TOP 1 @i=f2,@j=way FROM #temp WHERE flag=0
UPDATE #temp SET flag = 1 WHERE f2=@i
INSERT INTO #temp
     SELECT @j+','+f2,f1,f2,0 FROM TB t WHERE f1=@i AND f2 NOT IN (SELECT f1 FROM #temp)
END

SELECT STUFF(way,1,1,'') FROM #temp WHERE RIGHT(way,LEN(@end))=@end

/*
A,F,I
A,B,C,I
A,B,H,I
*/

DROP TABLE #temp

drop table [TB]

[其他解释]

USE test
GO


-->生成表t1
if object_id('t1') is not null 
drop table t1
Go
Create table t1([f1] nvarchar(1),[f2] nvarchar(1))
Insert into t1 
 
Select N'A',N'B'
Union all Select N'A',N'F'
Union all Select N'A',N'G'
Union all Select N'B',N'C'
Union all Select N'B',N'G'
Union all Select N'B',N'H'
Union all Select N'B',N'A'
Union all Select N'C',N'B'
Union all Select N'C',N'H'
Union all Select N'C',N'I'
Union all Select N'C',N'D'
Union all Select N'D',N'C'
Union all Select N'D',N'I'
Union all Select N'D',N'J'
Union all Select N'E',N'J'
Union all Select N'E',N'D'
Union all Select N'F',N'A'
Union all Select N'F',N'G'
Union all Select N'G',N'A'
Union all Select N'G',N'B'
Union all Select N'G',N'H'
Union all Select N'G',N'F'
Union all Select N'H',N'G'
Union all Select N'H',N'B'
Union all Select N'H',N'C'
Union all Select N'H',N'I'
Union all Select N'I',N'H'
Union all Select N'I',N'C'
Union all Select N'I',N'D'
Union all Select N'I',N'F'
Union all Select N'J',N'I'
Union all Select N'J',N'D'
Union all Select N'J',N'E'



DECLARE @startPoint NVARCHAR(1),@endPoint NVARCHAR(1)

SELECT @startPoint='A',@endPoint='I'

IF object_id('tempdb..#Result')IS NOT NULL
DROP TABLE #Result
;WITH c1 AS (
SELECT 
0 AS Row
,f1 AS startPoint
,f2 AS endPoint
,CONVERT(NVARCHAR(max),f1+' - >'+f2) AS Route
FROM t1
UNION ALL
SELECT 
b.Row+1
,b.startPoint
,a.f2
,CONVERT(NVARCHAR(MAX),b.Route+' - >'+a.f2)
FROM t1AS a
INNER JOIN c1AS b ON a.f1=b.endPoint
WHERE CHARINDEX(a.f2,b.Route)=0
)
SELECT 
Row+2AS 步數
,startPoint AS 始點
,endPointAS 終點
,RouteAS 路線 
INTO #Result
FROM c1
WHERE startPoint=@startPoint 
AND endPoint=@endPoint
ORDER BY 步數
OPTION (MAXRECURSION 0)


SELECT
a.步數
,a.始點
,a.終點
,a.路線
,CONVERT(BIT,CASE WHEN NOT EXISTS(SELECT 1 FROM #Result AS x
WHERE x.步數<a.步數
)
THEN 1
ELSE 0
END) AS 是否最佳路線
FROM #Result AS a

/*
步數        始點 終點 路線 是否最佳路線
----------- ---- ---- ------------------------------------------ -------------
4           A    I    A - >G - >H - >I                           1
4           A    I    A - >B - >H - >I                           1
4           A    I    A - >B - >C - >I                           1 
 
5           A    I    A - >B - >C - >D - >I                      0
5           A    I    A - >B - >C - >H - >I                      0
5           A    I    A - >B - >H - >C - >I                      0
5           A    I    A - >B - >G - >H - >I                      0
5           A    I    A - >G - >H - >C - >I                      0
5           A    I    A - >G - >B - >H - >I                      0
5           A    I    A - >G - >B - >C - >I                      0
5           A    I    A - >F - >G - >H - >I                      0
6           A    I    A - >F - >G - >H - >C - >I                 0
6           A    I    A - >G - >B - >C - >D - >I                 0
6           A    I    A - >G - >H - >B - >C - >I                 0
6           A    I    A - >G - >B - >H - >C - >I                 0
6           A    I    A - >G - >H - >C - >D - >I                 0 
 
6           A    I    A - >B - >G - >H - >C - >I                 0
6           A    I    A - >B - >H - >C - >D - >I                 0
6           A    I    A - >F - >G - >B - >H - >I                 0
6           A    I    A - >F - >G - >B - >C - >I                 0
6           A    I    A - >B - >C - >D - >J - >I                 0
6           A    I    A - >G - >B - >C - >H - >I                 0
7           A    I    A - >F - >G - >B - >C - >H - >I            0
7           A    I    A - >F - >G - >B - >C - >D - >I            0
7           A    I    A - >F - >G - >H - >B - >C - >I            0
7           A    I    A - >F - >G - >B - >H - >C - >I            0
7           A    I    A - >B - >H - >C - >D - >J - >I            0
7           A    I    A - >B - >G - >H - >C - >D - >I            0
7           A    I    A - >G - >H - >C - >D - >J - >I            0
7           A    I    A - >G - >B - >H - >C - >D - >I            0 
 
7           A    I    A - >G - >H - >B - >C - >D - >I            0
7           A    I    A - >G - >B - >C - >D - >J - >I            0
7           A    I    A - >F - >G - >H - >C - >D - >I            0
8           A    I    A - >F - >G - >H - >C - >D - >J - >I       0
8           A    I    A - >G - >H - >B - >C - >D - >J - >I       0
8           A    I    A - >G - >B - >H - >C - >D - >J - >I       0
8           A    I    A - >B - >G - >H - >C - >D - >J - >I       0
8           A    I    A - >F - >G - >B - >H - >C - >D - >I       0
8           A    I    A - >F - >G - >H - >B - >C - >D - >I       0
8           A    I    A - >F - >G - >B - >C - >D - >J - >I       0
9           A    I    A - >F - >G - >H - >B - >C - >D - >J - >I  0
9           A    I    A - >F - >G - >B - >H - >C - >D - >J - >I  0
*/

[其他解释]
 

create table #y([f1] varchar(1),[f2] varchar(1))
insert #y 
select 'A','B' union all 
select 'A','F' union all 
select 'A','G' union all 
select 'B','C' union all 
select 'B','G' union all 
select 'B','H' union all  
 
select 'B','A' union all 
select 'C','B' union all 
select 'C','H' union all 
select 'C','I' union all 
select 'C','D' union all 
select 'D','C' union all 
select 'D','I' union all 
select 'D','J' union all 
select 'E','J' union all 
select 'E','D' union all 
select 'F','A' union all 
select 'F','G' union all 
select 'G','A' union all 
select 'G','B' union all 
select 'G','H' union all 
select 'G','F' union all 
select 'H','G' union all 
select 'H','B' union all 
select 'H','C' union all 
select 'H','I' union all 
select 'I','H' union all 
select 'I','C' union all 
select 'I','D' union all 
select 'I','F' union all 
select 'J','I' union all 
select 'J','D' union all 
select 'J','E' 
GO 
 WITH tb_a AS( 
    SELECT #y.f1,#y.f2,[result]=CAST(#y.f1 +'->' + #y.f2 AS VARCHAR(1500)) FROM #y WHERE #y.f1='a' 
    UNION ALL    
    SELECT #y.f1,#y.f2,[result]=CAST([result]+ '->' + #y.f2 AS VARCHAR(1500)) FROM tb_a a INNER JOIN #y ON a.f2=#y.f1  WHERE charIndex(#y.f2,a.[result])<1
 )
 SELECT * FROM tb_a WHERE result LIKE '%i'

[其他解释]

--> 测试数据：[TB]
if object_id('[TB]') is not null drop table [TB]
GO
create table [TB]([f1] varchar(1),[f2] varchar(1))
insert [TB]
select 'A','B' union all
select 'A','F' union all
select 'A','G' union all
select 'B','C' union all
select 'B','G' union all
select 'B','H' union all
select 'B','A' union all
select 'C','B' union all
select 'C','H' union all
select 'C','I' union all
select 'C','D' union all
select 'D','C' union all
select 'D','I' union all
select 'D','J' union all
select 'E','J' union all
select 'E','D' union all
select 'F','A' union all
select 'F','G' union all
select 'G','A' union all
select 'G','B' union all
select 'G','H' union all
select 'G','F' union all
select 'H','G' union all
select 'H','B' union all
select 'H','C' union all
select 'H','I' union all
select 'I','H' union all
select 'I','C' union all
select 'I','D' union all
select 'I','F' union all
select 'J','I' union all
select 'J','D' union all
select 'J','E'



DECLARE @start VARCHAR(10),@end VARCHAR(10)
SET @start='A'
SET @end='I'

IF OBJECT_ID('tempdb..#temp') IS NOT NULL 
 
     DROP TABLE #temp

CREATE TABLE #temp(
way VARCHAR(MAX),
f1 VARCHAR(10),
f2 VARCHAR(10),
flag int)


INSERT INTO #temp
SELECT '-'+f1+'-'+f2,f1,f2,0 FROM tb WHERE f1=@start

WHILE (SELECT COUNT(1) FROM #temp WHERE flag=0)>0
BEGIN
DECLARE @i VARCHAR(10),@j VARCHAR(MAX)
SELECT TOP 1 @i=f2,@j=way FROM #temp WHERE flag=0
UPDATE #temp SET flag = 1 WHERE f2=@i
INSERT INTO #temp
     SELECT @j+'-'+f2,f1,f2,0 FROM TB t WHERE f1=@i AND f2 NOT IN (SELECT f1 FROM #temp WHERE way<@j)
END

SELECT STUFF(way,1,1,'') FROM #temp WHERE RIGHT(way,LEN(@end))=@end

/*
A-B-C-I
A-B-H-I
A-B-C-D-I
A-B-C-D-C-I
A-B-C-D-C-H-I
A-B-C-D-C-D-I
A-B-C-D-C-D-J-I
A-B-C-D-C-H-I-H-I
A-B-C-D-C-D-J-I-H-I
A-B-C-D-C-D-J-E-J-I
*/

DROP TABLE #temp

drop table [TB]

[其他解释]
多谢高手相助，
最后三条我写错了
不是
F I
F D
F E
应该是
J I
J D
J E

我测试了一下，这种方式可以查找出路径，但好像不全啊。
[其他解释]

DECLARE @start VARCHAR(10),@end VARCHAR(10)
SET @start='A'
SET @end='I'

IF OBJECT_ID('tempdb..#temp') IS NOT NULL
     DROP TABLE #temp

CREATE TABLE #temp(
way VARCHAR(MAX),
f1 VARCHAR(10),
f2 VARCHAR(10),
flag int)


INSERT INTO #temp
SELECT '-'+f1+'-'+f2,f1,f2,0 FROM tb WHERE f1=@start

WHILE (SELECT COUNT(1) FROM #temp WHERE flag=0)>0
BEGIN
DECLARE @i VARCHAR(10),@j VARCHAR(MAX)
SELECT TOP 1 @i=f2,@j=way FROM #temp WHERE flag=0
UPDATE #temp SET flag = 1 WHERE f2=@i
INSERT INTO #temp
     SELECT @j+'-'+f2,f1,f2,0 FROM TB t WHERE f1=@i AND f2 NOT IN (SELECT f1 FROM #temp WHERE way<=@j)
END

SELECT STUFF(way,1,1,'') FROM #temp WHERE RIGHT(way,LEN(@end))=@end

/*
A-B-C-I
A-B-H-I
A-B-C-D-I
*/

DROP TABLE #temp

[其他解释]
最后一个加了筛选条件，应该可以了
[其他解释]
先谢了，这个还是不全面啊，从A点出来的 A-B ,A-F,A-G  这三条路线都能够到达I点，而且还不止一条
A-G-H-I
A-F-G-H-I
[其他解释]
多谢了。我根据你前面的那个方法稍微改动一下就可以了。
[其他解释]
上面三位兄弟的方法都可以。

查看更多 下一篇