SQL Server : Longest Path

Question

In SQL Server, I have the (From,To) in columns From and To in a table.

How do I find the longest path between any two npoints given as input? For example, if the input is 1,17 then the answer should be 1 - 5 - 13 - 17

define what is a path here? is this `(x,y)` coordinates in a Cartesian plane? or more like `From To`? I dont see how your example is the **longest** path. Also you mention path between two nodes `(1,17)`. What node is 1 and what node is 17? Is there an `ID` missing? — Juan Carlos Oropeza, Dec 28 '17 at 14:56
Yes, it is more like From-To. I updated the question based on your comment. Thanks. — Jhudge, Dec 28 '17 at 14:59
No, the values in From and To in any given row will always be different. — Jhudge, Dec 28 '17 at 15:03
You need a recursive cte https://technet.microsoft.com/en-us/library/ms186243(v=sql.105).aspx — Juan Carlos Oropeza, Dec 28 '17 at 15:04

score 2 · Answer 1 · answered Dec 28 '17 at 15:16

2

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

From 1 to 17 there is a tie with two path with length 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 |

answered Dec 28 '17 at 15:16

Juan Carlos Oropeza

47,252
12
78
118

Thanks Juan. With my dataset, I'm getting this error: The statement terminated. The maximum recursion 100 has been exhausted before statement completion. Is it possible to specify the inputs inside the CTE? – Jhudge Dec 28 '17 at 15:24
That mean either you have some cycles or too long paths. add `where length < 100` – Juan Carlos Oropeza Dec 28 '17 at 15:36
You can change the max recursion to allow infinite recursion if the problem are long path. But if you have cycles your query wont end. https://stackoverflow.com/questions/9650045/the-maximum-recursion-100-has-been-exhausted-before-statement-completion – Juan Carlos Oropeza Dec 28 '17 at 15:37

SQL Server : Longest Path

1 Answers1