SQL Server 2008 CTE Рассчитайте все пути между двумя точками

Question

Я стараюсь много вещей с CTE, и у меня все еще есть проблемы У меня есть таблица, которая нравится, например: (В моей таблице есть 6 873 368 строк)

+--------+----------+---------+ 
| 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 | 
+--------+----------+---------+ 

Я бы хотел, чтобы весь путь Grom источника: 1 до пункта назначения 4, например для Somes линий он работает отлично с КТР, но с числом строк у меня это заняло слишком много времени (более 29 минут для нескольких решений).

Я стараюсь это:

;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 выход я excpeted что-то вроде этого:

+--------+----------+----------------+--------+--------+ 
| 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  | 
+--------+----------+---------+------+--------+--------+ 

Я просто хочу, чтобы вычислить путь мне нужно не весь путь от всей точки, Жюст путь от А до Б, например :) У вас есть идея, как я могу сделать это за меньшее время, если это возможно?

Я пробовал много вещей, но я понятия не имею, как я могу остановить CTE, когда достигнет значения желания?

У меня есть этот результат до того, как выбрать * из КТР предложения:

+--------+----------+----------------+--------+--------+ 
    | 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  | 
    +--------+----------+---------+------+--------+--------+ 

Но я хотел бы, чтобы остановить результат durring КТР в Dest: 4 Спасибо :)

Answer 1

Мне нравится ваше мышление с CTE, но делать NOT LIKE '% + .. очень неэффективно.

У меня есть попытка использовать другой подход для этого сравнения, используя двоичную математику вместо сравнения строк!

В основном мы храним «Путь» в виде суммы 2^(Destination).
Таким образом, маршрут, который отправил Destination ID 1 & 3 будет 2^1 + 2^3 = 2 + 8 = 10.
Надеюсь, вы увидите, что это эффективный способ хранения всех посещенных пунктов назначения (но не по порядку).
Тогда, чтобы увидеть, если шаг был посещен в прошлом мы сравниваем только немного в вопросе

Вы можете сделать это, беря 2 MOD (2^(current destinationID + 1)) (в основном удаляя все более высокое назначение из сохраненного пути бинарного - оставляя только места назначения в там с идентификаторами, меньшими или равными текущему получателю), и проверьте, что этот номер меньше 2^(current destination ID).

Примечание - Используя одно поле для хранения двоичного путь поля позволит Идентификаторы от 0 до 30 с целым числом в качестве типа данных (2^31 - 1 это максимальное число, которое может быть сохранено)
Таким образом, с помощью INT Макса ID - 30
Если мы используем BIGINT, тогда максимальный ID равен 62
Если мы используем DECIMAL (38,0), тогда максимальный ID равен 125 (хотя его 17-байтное/136-битное поле maxID равно 10^38 - 1)

Не знаете, насколько хорошо я это объяснил, так что это на практике ...

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 

это дает желаемый результат (более или менее)

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 

Вы также заметите, что я также проверить, что мы не выше максимального числа шагов в само- КТР join