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