SQL Server : 최장 경로

Question

SQL Server에서 From 및 To 열을 테이블에 포함합니다.

From To 
- - 
1 5 
1 7 
1 8 
1 17 
2 11 
3 5 
4 7 
5 12 
5 13 
5 17 
8 13 
8 17 
13 17 

어떻게 입력으로 주어진 두 npoint 사이에서 가장 긴 경로를 찾으십니까? 5 - - 13-17

Answer 1

SQL DEMO

WITH Path (FromID, ToID, Length, nodes) AS (
    SELECT t1.FromID, t1.ToID, 0 as Length, 
      CAST(t1.FromID AS VARCHAR(max)) +'-'+ 
      CAST(t1.ToID AS VARCHAR(max)) as nodes 
    FROM Table1 t1 
    UNION ALL 
    SELECT P.FromID, t2.ToID, P.Length + 1, 
      P.nodes + '-' + CAST(t2.ToID AS VARCHAR(max)) as nodes 
    FROM Table1 t2 
    JOIN Path P 
     ON P.ToID = t2.FromID 
) 
SELECT * 
FROM Path 
WHERE FromID = 1 
    and ToID = 17 
Order by Length 

OUTPUT 17 행 1에서

가 입력이 1,17 인 경우, 예를 들어, 그 응답은 1이어야 길이가 2 인 경로가있는 넥타이

| FromID | ToID | Length |  nodes | 
|--------|------|--------|-----------| 
|  1 | 17 |  0 |  1-17 | 
|  1 | 17 |  1 | 1-8-17 | 
|  1 | 17 |  1 | 1-5-17 | 
|  1 | 17 |  2 | 1-5-13-17 | 
|  1 | 17 |  2 | 1-8-13-17 |