Оптимальный путь в лабиринте MS SQL

[Аватар]

По мотивам темы http://programmersforum.ru/showthread.php?t=268634

Есть таблица

CREATE TABLE Maze (
       Room1                varchar(20) NOT NULL,
       Room2                varchar(20) NOT NULL
)
go

ALTER TABLE Maze
       ADD PRIMARY KEY (Room1, Room2)
go

Каждая запись - дверь между комнатами. Найти оптимальный путь между двумя заданными комнатами. Одним запросом - без рекурсивного не получится.

Забил в таблицу данные, кому интересно скрипты прилагаются. Получил без рекурсии, наверняка можно и покороче, не важно

DECLARE @RoomIn varchar(4),
        @RoomOut varchar(4),
        @Room varchar(4),
        @Room1 varchar(4),
        @Room2 varchar(4),
        @NumbLevel int,
        @Count int
SET @RoomIn='10E'
SET @RoomOut='02D'
DECLARE @Temp1 TABLE(Room1 varchar(4) NOT NULL, NumbLevel int not NULL)
DECLARE @Temp2 TABLE(Room1 varchar(4) NOT NULL, Room2 varchar(4) NOT NULL, NumbLevel int not NULL, Path int NOT NULL)
INSERT INTO @Temp1 VALUES(@RoomIn,0)
SET @NumbLevel=0
SET @Count=0
WHILE 1=1 BEGIN
  declare Cursor1 cursor for
    SELECT Room1 FROM @Temp1 WHERE NumbLevel=@NumbLevel
  open Cursor1
  fetch next from Cursor1 into @Room
  while @@FETCH_STATUS=0 begin
    declare Cursor2 cursor for
      SELECT CASE WHEN Room1=@Room THEN Room1 ELSE Room2 END AS Room1,
             CASE WHEN Room1=@Room THEN Room2 ELSE Room1 END AS Room2
        FROM Maze
        WHERE Room1<>Room2 AND (Room1=@Room OR Room2=@Room)
    open Cursor2
    fetch next from Cursor2 into @Room1,@Room2
    while @@FETCH_STATUS=0 begin
      IF NOT EXISTS(SELECT 1 FROM @Temp2 WHERE Room2=@Room2) BEGIN
        INSERT INTO @Temp2 VALUES(@Room1,@Room2,@NumbLevel+1,0)
        IF @Room2=@RoomOut BEGIN
          DELETE @Temp1 WHERE NumbLevel>@NumbLevel
          SET @Count=1
          BREAK
        END
        INSERT INTO @Temp1 VALUES(@Room2,@NumbLevel+1)
      END
      fetch next from Cursor2 into @Room1,@Room2
    END
    close Cursor2
    deallocate Cursor2
    IF @Count=1 BREAK
    fetch next from Cursor1 into @Room
  END
  close Cursor1
  deallocate Cursor1
  DELETE @Temp1 WHERE NumbLevel=@NumbLevel
  SET @NumbLevel=@NumbLevel+1
  IF NOT EXISTS(SELECT 1 FROM @Temp1 WHERE NumbLevel=@NumbLevel) BREAK
END
IF @Count=1 BEGIN
  SET @Room=@RoomOut
  WHILE 1=1 BEGIN
    UPDATE @Temp2 SET @Room1=Room1=Room1,Path=1 WHERE Room2=@Room
    IF @Room1=@RoomIn BEGIN
      DELETE @Temp2 WHERE Path=0
      BREAK
    END
    SET @Room=@Room1
  END
END
ELSE DELETE @Temp2
SELECT Room1, Room2, NumbLevel FROM @Temp2

Результат

Room1 Room2 NumbLevel
10E   10F   1
10F   09F   2
09F   08F   3
08F   07F   4
07F   07G   5
07G   06G   6
06G   05G   7
05G   04G   8
04G   04F   9
04F   04E   10
04E   03E   11
03E   02E   12
02E   01E   13
01E   01D   14
01D   02D   15

Теперь рекурсивно, знаю только теоретически, на практике по сути первый раз

WITH RepUnion (room1, room2) AS
(
SELECT room1, room2 FROM maze WHERE room1<>room2
UNION
SELECT room2, room1 FROM maze WHERE room1<>room2
),
RepRecurs(room1, room2, qq, ee) AS 
(
SELECT room1, room2, CAST('#'+room1+'#'+room2+'#' AS varchar(max)) AS qq, 1 AS ee FROM RepUnion WHERE room1='10E'
UNION ALL
SELECT u.room1, u.room2, CAST(r.qq+u.room2+'#' AS varchar(max)), r.ee + 1
  FROM RepUnion AS u INNER JOIN RepRecurs AS r ON r.room2=u.room1 AND r.qq NOT LIKE '%#'+u.room2+'#%'
)
SELECT room1, room2, ee, qq FROM RepRecurs WHERE room2='02D' ORDER BY 3,1,2
--SELECT room1, room2, ee, qq FROM RepRecurs ORDER BY 3,1,2

Результат в 1-ой строке и путь совпал с предыдущим вариантом

room1 room2 ee qq
01D   02D   15 #10E#10F#09F#08F#07F#07G#06G#05G#04G#04F#04E#03E#02E#01E#01D#02D#
02C   02D   23 #10E#10F#09F#08F#07F#07G#06G#05G#04G#04F#04E#05E#05D#04D#03D#03C#04C#04B#04A#03A#03B#02B#02C#02D#
02C   02D   25 #10E#10F#09F#08F#07F#07G#06G#05G#04G#04F#04E#05E#05D#06D#06C#07C#07B#06B#05B#04B#04A#03A#03B#02B#02C#02D#
02C   02D   27 #10E#10F#09F#08F#07F#07G#06G#05G#04G#04F#04E#05E#05D#04D#03D#03C#04C#04B#04A#03A#03B#02B#02A#01A#01B#01C#02C#02D#
02C   02D   29 #10E#10F#09F#08F#07F#07G#06G#05G#04G#04F#04E#05E#05D#06D#06C#07C#07B#06B#05B#04B#04A#03A#03B#02B#02A#01A#01B#01C#02C#02D#

Теперь вопрос - почему несколько записей с конечным элементом "02D", хотя в запросе тот NOT LIKE должен не допустить этого. NOT LIKE работает, иначе рекурсия бы зациклилась. Почему не всегда? Предположительно, что в несколько частично не зависимых потоков выборка идет

[Аватар]

Вроде разобрался почему так. Хабр помог. Формально так - сначала выполняется первый запрос. Потом к его результатам добавляются результаты второго запроса, где данные таблицы RepRecurs – это результат первого запроса. Затем снова выполняется второй запрос, но данные таблицы RepRecurs – это уже результат предыдущего выполнения второго запроса. И так далее. СУБД на самом деле работает не совсем так, но результат будет таким же, как результат работы описанного формального алгоритма.