SQL Server 2008 CTE Calculate all paths between two points
I try a lot of things with CTEs and still have problems I have a table that looks like this, for example: (In my table I have 6 873 368 rows )
+--------+----------+---------+
| SOURCE | DEST | DISTANCE|
+--------+----------+---------+
| 1 | 1 | 125 |
| 1 | 2 | 100 |
| 1 | 3 | 002 |
| 1 | 4 | 058 |
| 2 | 1 | 000 |
| 2 | 2 | 050 |
| 2 | 3 | 125 |
| 2 | 4 | 785 |
| 3 | 1 | 000 |
| 3 | 2 | 050 |
| 3 | 3 | 125 |
| 3 | 4 | 785 |
+--------+----------+---------+
I would like it all the way to go grom Source: 1 to destination 4, for example For somes strings it works fine with CTEs, but with numeric strings I was taking too long (over 29 minutes for multiple solutions).
I am trying this:
;WITH T_Route (CONNECTION_DEST, STEPS, WEIGTH, WAY, RESSOURCE_SRC,RESSOURCE_DEST,RESSOURCE_TYPE)
AS
(SELECT DISTINCT C.CONNECTION_SRC
, 0
, 0
, @SRC
, @SRC
, @SRC
, 1
FROM #CheminCircuit AS C
WHERE C.RESSOURCE_SRC = @SRC
UNION ALL
SELECT arrival.CONNECTION_DEST
, departure.STEPS + 1
, departure.WEIGTH + arrival.VOL
, departure.WAY + ',' + arrival.RESSOURCE_DEST
, departure.RESSOURCE_DEST
, arrival.RESSOURCE_DEST
, arrival.RESSOURCE_TYPE
FROM #CheminCircuit AS arrival
INNER JOIN T_Route AS departure ON departure.CONNECTION_DEST = case when departure.STEPS < @STEPS then arrival.CONNECTION_SRC else 0 end -- AND arrival.RESSOURCE_SRC not like '%' + @DEST + '%' AND departure.STEPS < @STEPS
WHERE departure.WAY NOT LIKE '%,' + arrival.RESSOURCE_DEST + '%'
AND (arrival.RESSOURCE_TYPE NOT IN (SELECT T.[Index] FROM Type_Ressource T WHERE T.[Index] IN (1)) OR arrival.RESSOURCE_DEST IN (@SRC,@DEST))
)
,SHORT (WEIGTH)
AS
(SELECT WEIGTH
FROM T_Route
WHERE RESSOURCE_DEST = @DEST)
SELECT *
FROM T_Route AS T
Th output i excpeted looks something like this:
+--------+----------+----------------+--------+--------+
| SOURCE | DEST | DISTANCE | TIME |STEPS |
+--------+----------+----------------+--------+--------+
| 1 | 4 | 1->2->3->4 | 285 | 2 |
| 1 | 4 | 1->4 | 183 | 0 |
| 1 | 4 | 1->3->4 | 185 | 1 |
| 1 | 4 | 1->2->4 | 283 | 1 |
+--------+----------+---------+------+--------+--------+
I just want to calculate the way that I need not all the way from the whole point, for example, the path from A to B :) Do you have an idea how I can do this in less time, if possible?
I've tried a lot of things, but I have no idea how can I stop the CTE when it reaches the desire value?
I have this result before selecting * from the CTE clause:
+--------+----------+----------------+--------+--------+
| SOURCE | DEST | DISTANCE | TIME |STEPS |
+--------+----------+----------------+--------+--------+
| 1 | 4 | 1->2->4->3 | 285 | 2 |
| 1 | 4 | 1->4->1 | 183 | 0 |
| 1 | 4 | 1->3->4->2->1 | 185 | 1 |
| 1 | 4 | 1->2->4 | 283 | 1 |
+--------+----------+---------+------+--------+--------+
But I would like to stop the result forcing the CTE at dest: 4 Thanks :)
source to share
I like your thinking with CTE, but it's NOT LIKE '% + ..
very inefficient to do .
I had to use a different approach for this comparison, using binary math instead of string comparison!
Basically, we store "Path" as a sum 2^(Destination)
.
So the route that went through destination IDs 1 and 3 will be 2^1 + 2^3 = 2 + 8 = 10
.
Hopefully you can see that this is an efficient way to store all visited destinations (but not in order).
Then, to see if a step has been visited in the past, we only compare this bit
You can do this by taking 2 MOD (2^(current destinationID + 1))
(basically removing all higher-order destinations from the binary of the stored path - leaving only destinations with IDs less than or equal to the current recipient there) and check that this number is less than 2 ^ (current destination ID)
.
Note. Using a single field to store a binary path allows identifiers from 0 to 30 with an integer as the data type ( 2^31 - 1
is the maximum amount that can be stored)
Therefore, using INT, the maximum ID is 30
If we use BIGINT then the maximum ID is 62 If we use DECIMAL (38,0) then max ID is 125 (although its 17 byte / 136 bit maxID field is 10 ^ 38 -1)
Not sure how well I explained this, so this is in practice ...
DECLARE @CheminCircuit TABLE([Source] INT, Dest INT, DISTANCE INT)
INSERT @CheminCircuit
( Source, Dest, DISTANCE )
VALUES ( 1,1,125), (1,2,100),(1,3,2),(1,4,58),(2,1,0),
(2,2,50),(2,3,125),(2,4,785),(3,1,0),(3,2,50),(3,3,125),(3,4,785)
DECLARE @maxSteps INT
SELECT @maxSteps = COUNT(DISTINCT Dest)
FROM @CheminCircuit AS cc WHERE Dest <> @src
; WITH T_Route ([Source], [Dest], Distance, Way, WayBin, STEPS)
AS(
SELECT Source,
Dest,
DISTANCE,
CAST(CAST(@src AS NVARCHAR(255)) + '->' + CAST(Dest AS NVARCHAR(255)) AS NVARCHAR(255)),
POWER(2,Source) + POWER(2,Dest),
1
FROM @CheminCircuit AS cc WHERE Source = @src AND cc.Dest <> cc.Source
UNION ALL
SELECT T_Route.Source, cc.Dest,
T_Route.Distance + cc.DISTANCE,
CAST( T_Route.Way + '->' + CAST(cc.Dest AS NVARCHAR(255)) AS NVARCHAR(255)),
T_Route.WayBin + POWER(2,cc.Dest),
T_Route.STEPS + 1
FROM @CheminCircuit AS cc
JOIN T_Route ON T_Route.Dest = cc.Source
WHERE T_Route.STEPS < @maxSteps
AND T_Route.Dest <> @dst AND cc.Dest <> cc.Source
AND (T_Route.WayBin % POWER(2, cc.Dest+1) ) < POWER(2,cc.Dest)
)
SELECT * FROM T_Route WHERE Dest = @dst
this gives the desired result (more or less)
Source Dest Distance Way WayBin STEPS
------ ---- -------- -- ------ -----
1 4 58 1->4 18 1
1 4 787 1->3->4 26 2
1 4 837 1->3->2->4 30 3
1 4 885 1->2->4 22 2
1 4 1010 1->2->3->4 30 3
You will also notice that I am also checking that we are not exceeding the maximum number of steps in the CTE self-join
source to share