两点之间的路径

Question

我有一个 table，两点之间有连接：

RidgeId PointId1    PointId2
1   1   2
2   3   2
3   17  10
4   18  10
6   18  11
7   11  3
8   4   1
9   13  4
10  16  13
11  15  16
12  5   15
13  19  5
14  20  19
15  21  20
16  8   21
17  12  8
18  6   12

我想找到两点之间的路径。 F。例如

从 3 到 10

3、11
11、18
18, 10

如何编写查询以获得此结果？

编辑：

如何像这样添加有关与原始行的一致连接的信息：

Answer 1

您可以为此使用递归 CTE。由于您可以有多个路由，因此 return 结果集的最简单方法是 return 它作为 JSON

有两个锚点和两个递归，因为我们可以从 Point1 到 Point2 或 v.v。对于每个节点

DECLARE @start int = 3;
DECLARE @end int = 10;

WITH cte AS (
    SELECT
      Point2 = p.PointId2,
      p.RidgeId,
      Json = (
          SELECT p.RidgeId, p.PointId1, p.PointId2
          FOR JSON PATH
      )
    FROM Points p
    WHERE p.PointId1 = @start
    
    UNION ALL
    
    SELECT
      Point2 = p.PointId1,
      p.RidgeId,
      Json = (
          SELECT p.RidgeId, p.PointId1, p.PointId2
          FOR JSON PATH
      )
    FROM Points p
    WHERE p.PointId2 = @start
    
    UNION ALL
    
    SELECT
      Point2 = p.PointId2,
      p.RidgeId,
      Json = JSON_MODIFY(cte.Json, 'append $', JSON_QUERY((
          SELECT p.RidgeId, p.PointId1, p.PointId2
          FOR JSON PATH, WITHOUT_ARRAY_WRAPPER
      )))
    FROM Points p
    JOIN cte ON cte.Point2 = p.PointId1
    WHERE p.RidgeId <> cte.RidgeId

    UNION ALL
    
    SELECT
      Point2 = p.PointId1,
      p.RidgeId,
      Json = JSON_MODIFY(cte.Json, 'append $', JSON_QUERY((
          SELECT p.RidgeId, p.PointId1, p.PointId2
          FOR JSON PATH, WITHOUT_ARRAY_WRAPPER
      )))
    FROM Points p
    JOIN cte ON cte.Point2 = p.PointId2
    WHERE p.RidgeId <> cte.RidgeId
)

SELECT Json
FROM cte
WHERE cte.Point2 = @end;

Result
[{"RidgeId":7,"PointId1":11,"PointId2":3}, {"RidgeId":6,"PointId1":18,"PointId2":11}, {"RidgeId":4,"PointId1":18,"PointId2":10}]

db<>fiddle

这不能很好地处理节点中的循环。理想情况下，您应该通过打破每个递归部分中的 JSON 并检查我们不会回到自己身上来检查是否没有循环

两点之间的路径

Path between two points

sql

sql-server

sql-server-2016

sql-server-2017