Алгоритм решения динамической задачи поиска кратчайших расстояний в графе

Автор(ы): Ураков А.Р., Тимеряев Т.В.

Название статьи: Алгоритм решения динамической задачи поиска кратчайших расстояний в графе

Выпуск: 65

Рубрика: Информационные технологии в управлении

Год: 2017

Библиография: Ураков А.Р., Тимеряев Т.В. Алгоритм решения динамической задачи поиска кратчайших расстояний в графе / Управление большими системами. Выпуск 65. М.: ИПУ РАН, 2017. С.60-86. URL: https://doi.org/10.25728/ubs.2017.65.4

Дата опубликования: 31.01.2017

Ключевые слова: динамические кратчайшие расстояния, актуализация графа, коррекция графа, равноудаленные точки

Аннотация: Рассматривается полностью динамическая задача поиска кратчайших расстояний между всеми парами вершин неориентированного графа. Для данной задачи предлагается метод решения, учитывающий все возможные изменения расстояний в графе с помощью процедур добавления и удаления ребра. Для процедуры удаления ребра предложен алгоритм, использующий понятие точек, равноудаленных от вершин, инцидентных удаляемому ребру. Алгоритм позволяет существенно уменьшить время решения и объем используемой памяти в практических сценариях. Для доказательства практической эффективности предложенного метода решения произведен вычислительный эксперимент с использованием известных быстрых статических и динамических алгоритмов.

Author(s): Urakov A., Timeryaev T.

Article title: Algorithm for dynamic all-pairs distances in graph

Issue: 65

Year: 2017

Keywords: dynamic graph distances, graph update, equidistant points, graph actualization

Abstract: Fully dynamic all-pairs graph distances problem for undirected graphs with positive edge weights is considered. Edge weights can change arbitrary so distances between vertices should be kept actual. We propose an algorithm taking into account all possible distance changes by the use of edge addition and deletion procedures. The developed algorithm uses the notion of points equidistant to the vertices incident to the edge being deleted for an edge deletion procedure. This allows to significantly reduce time and memory complexity of the graph distance actualization task in practical scenarios. The conducted computational experiments showed that the proposed algorithms outperforms the fastest known methods.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 3337; загрузок: 1194, за месяц: 22.

Назад