SQL - процедура нахождения путей в графе

Обновлено 13.09.09:

Есть таблица, определяющая взвешенный ориентированный граф, описана так

create table Connection (

con_id bigint not null,

con_type tinyint not null default 1, --тип соединения,

--возможные значения: 1,2,4,8 bin: 0001,0010,0100,1000

con_from bigint not null,--конечная вершина

con_to bigint not null,--начальная вершина

con_cost decimal not null,--стоимость соединения (вес)

con_time datetime not null, --время прохождения соединения (второй вариант веса)

constraint PK_CONNECTION primary key (con_id)

)

требуется написать процедуру, которая по заданным параметрам возвращает все возможные пути, соответствующие заданным параметрам.

Процедура:

create procedure dbo.sp_get_paths

@dst_from_id bigint,--начальная точка пути

@dst_via_ids nvarchar(2048) null, --строка, содержащая id пунктов, через которые должен пройти путь через запятую, в том порядке, как они указаны, т.о. путь должен начинаться с dst_from_id, проходить через некоторые пункты, в том числе через dst_via_ids в указанном порядке

@dst_to_id bigint,--конечная точка маршрута

@allowed_type int,--разрешенные типы соединений, которые можно использовать (маска)

@weight_is_cost bit, --если TRUE то в качестве веса соединения используется поле cost, в противном случае time

@max_path_length tinyint, --максимальное количество пунктов в пути

@max_path_count tinyint, --максимальное количество путей в результате

@max_path_cost decimal null,--максимальная суммарная стоимость пути (если задано)

@max_path_time datetime null, --максимальное суммарное время пути (если задано)

as

declare

begin

?

end

Возращает процедура таблицу с найденными путями, отсортированную по возрастанию суммарной стоимости(или суммарного времени),

в столбцах таблицы - пути, в рядах описание путя: - id соединений (con_id), предпоследние 3 ряда содержат суммарный вес пути: 2 ряда на суммарную стоимость (в первом ряду целая часть, во втором дробная), и последний ряд содержит общее время на путь, в минутах.

Все значения - bigint

пример:

path1 | path2 | path3

12 | 11 | 1

35 | 3 | 89

14 |18 | null

15 | null | null

34 |45 | 87 - стоимости 34.5,45.3,87.2

50 |30 | 20

85 |1405 |741 - длительности 01:25:00,23:25:00,12:21:00

максимально в таблице может быть @max_path_count столбцов и @max_path_length+3 рядов.

Если ничего не найдено возвращается таблица

path1

0

Если произошла ошибка, то нужно кидать пользовательское исключение с описанием и кодом ошибки.

Целевая БД - MSSQL 2005

Процедура должна быть максимально оптимизирована.

Допускается изменение описания таблицы с графами и входных параметров процедуры для оптимизации, но только при условии согласования со мной.

Предполагается, что базе будет(максимально) порядка 10^9 записей (в таблице Connection)

и где-то 10^4 в таблице Destination