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

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