多条路线的查找问题
表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
[其他解释]
多谢了。我根据你前面的那个方法稍微改动一下就可以了。
[其他解释]
上面三位兄弟的方法都可以。