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

Web/сайты Прочее

Был(а) онлайн: 26.04.20 14:45
Umen 26 лет

1.0 Был(а) онлайн: 26.04.20 14:45

Недавно
Обновлено 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, --время прохождения соединения (2-й вариант веса)
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 Нет конкурсных работ

Чтобы добавить заявку к этому заказу, нужно войти или зарегистрироваться

Мой блок

26.04.20 14:45
Umen 26