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

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

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

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