Алгоритм Флойда-Уоршелла предназначен для нахождения кратчайших путей между всеми парами вершин во взвешенном графе. Этот алгоритм является одним из классических решений задачи о кратчайших путях и работает для графов с положительными и отрицательными весами ребер, но без отрицательных циклов.
Основные идеи алгоритма
Алгоритм использует матрицу расстояний, в которой на начальном этапе хранятся веса ребер графа (или бесконечность, если пути между вершинами непосредственного нет). Алгоритм следующим образом обновляет эту матрицу:
Инициализация. Создать матрицу D с размерами |V|x|V|, где V — множество вершин графа. Если существует ребро между вершинами i и j, то D[j] присваивается значение веса этого ребра; иначе — бесконечность.
Итерации. Последовательно проходит через все вершины графа в роли промежуточных узлов. Для каждой пары вершин (i, j) проверяется, сокращает ли путь через текущую промежуточную вершину k расстояние между i и j. Если это так, то D[j] обновляется:
[ D[j] = \min(D[j], D[k] + D[k][j]) ]
Отсутствие отрицательных циклов. Если после выполнения алгоритма на диагонали матрицы D обнаружены отрицательные значения, то граф содержит отрицательный цикл.
Преимущества и недостатки
- Преимущества: алгоритм прост в реализации, его сложность составляет O(n3), где n — количество вершин в графе. Он подходит для плотных графов.
- Недостатки: неэффективен для разреженных графов из-за своей временной сложности и требует большой памяти.
Алгоритм Флойда-Уоршелла широко используется в задачах маршрутизации, таких как нахождение кратчайших путей в сетях связи и транспортных сетях.
Категория: Информатика
Теги: алгоритмы, программирование, графы, теоретическая информатика