多条路线的查找问题

Question

表t1有两列 f1 表示站点编号 f2 表示与它相通的站点编号
列f1   列f2
A B
A F
A G
B C
B G
B H
B A
C B
C H
C I
C D
D C
D I
D J
E J
E D
F A
F G
G A
G B
G H
G F
H G
H B
H C
H I
I H
I C
I D
I F
F I
F D
F E现在如果我想查找 从A到 I怎么走路线，，应该会有多条路线， 想通过sql来实现查找方式，不知道可有好的方法。

Answer 1

--> 测试数据：[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 #tempCREATE 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=@startWHILE (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)
ENDSELECT 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 #tempdrop table [TB]

Answer 2

多谢高手相助，
最后三条我写错了
不是
F I
F D
F E
应该是
J I
J D
J E我测试了一下，这种方式可以查找出路径，但好像不全啊。

Answer 3

--> 测试数据：[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 #tempCREATE 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=@startWHILE (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)
ENDSELECT 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 #tempdrop table [TB]

Answer 4

DECLARE @start VARCHAR(10),@end VARCHAR(10)
SET @start='A'
SET @end='I'IF OBJECT_ID('tempdb..#temp') IS NOT NULL
     DROP TABLE #tempCREATE 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=@startWHILE (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)
ENDSELECT 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

Answer 5

先谢了，这个还是不全面啊，从A点出来的 A-B ,A-F,A-G  这三条路线都能够到达I点，而且还不止一条
A-G-H-I
A-F-G-H-I

Answer 6

 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'

Answer 7

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 t1 AS a
INNER JOIN c1 AS b ON a.f1=b.endPoint
WHERE CHARINDEX(a.f2,b.Route)=0
)
SELECT 
Row+2 AS 步數
,startPoint AS 始點
,endPoint AS 終點
,Route AS 路線 
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
*/