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