Нахождение кратчайших путей из заданной вершины во все остальные вершины графа

14 сентября 2018
530
Предметная область —
Отрасли по ОКВЭД —
Страна, регион, город Российская Федерация, Москва
Отличия от конкурентов —
Вид документа об охране ИС программа для ЭВМ
Номер документа ИС 201661026
Дата регистрации документа ИС 2016-01-11
Необходимые инвестиции для внедрения договорная
Сроки внедрения —
Стоимость предоставления технологии договорная
Наличие экспертного заключения Нет

Польза для потенциального потребителя

Программа предназначена для нахождения кратчайших путей и соответствующих расстояний от заданной вершины ориентированного графа до всех остальных вершин этого графа. Может найти применение при навигации по карте дорог, в том числе с учетом пробок, маршрутизации в сетях передачи данных, составлении планов эвакуации. Данная реализация предназначена для тестирования возможностей и быстродействия работы алгоритма на модели параллельной потоковой вычислительной системы. Программа реализует параллельный алгоритм Дельта-степпинг – модификация алгоритма Дейкстры. В программе имеется три независимых релакс-фильтра и есть возможность отключения любого из них. Релакс-фильтр это "устройство", которое прерывает активность в случае, когда ее новое расстояние не уменьшает старое.