Интернет конференция по проблемам теории и практики управленияНазвание: Алгоритм решения динамической задачи поиска кратчайших расстояний в графе
Автор: Тимофей Валерьевич Тимеряев
Соавторы:
Ураков А.Р.
Аннотация:
В статье рассматривается полностью динамическая задача поиска кратчайших расстояний между всеми парами вершин неориентированного графа. Для рассматриваемой задачи предлагается метод решения, учитывающий все возможные изменения расстояний в графе с помощью процедур добавления и удаления ребра. Для процедуры удаления ребра предложен алгоритм, использующий понятие точек равноудаленных от инцидентных удаляемому ребру вершин, что позволяет существенно уменьшить время решения и объем используемой памяти в практических сценариях. Произведено сравнения предложенного метода решения с известными, показывающее уменьшение времени счета в среднем в 30 раз на исследованных разреженных графах размерности 10000 вершин.
Ключевые слова:
динамические кратчайшие расстояния, актуализация графа, коррекция графа, равноудаленные точки
Автор: Тимофей Валерьевич Тимеряев
Соавторы:
Ураков А.Р.
Аннотация:
В статье рассматривается полностью динамическая задача поиска кратчайших расстояний между всеми парами вершин неориентированного графа. Для рассматриваемой задачи предлагается метод решения, учитывающий все возможные изменения расстояний в графе с помощью процедур добавления и удаления ребра. Для процедуры удаления ребра предложен алгоритм, использующий понятие точек равноудаленных от инцидентных удаляемому ребру вершин, что позволяет существенно уменьшить время решения и объем используемой памяти в практических сценариях. Произведено сравнения предложенного метода решения с известными, показывающее уменьшение времени счета в среднем в 30 раз на исследованных разреженных графах размерности 10000 вершин.
Ключевые слова:
динамические кратчайшие расстояния, актуализация графа, коррекция графа, равноудаленные точки