Алгоритм Флойда-Уоршелла предназначен для нахождения кратчайших путей между всеми парами вершин во взвешенном графе. Этот алгоритм является одним из классических решений задачи о кратчайших путях и работает для графов с положительными и отрицательными весами ребер, но без отрицательных циклов.

Основные идеи алгоритма

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

  1. Инициализация. Создать матрицу D с размерами |V|x|V|, где V — множество вершин графа. Если существует ребро между вершинами i и j, то Dj присваивается значение веса этого ребра; иначе — бесконечность.

  2. Итерации. Последовательно проходит через все вершины графа в роли промежуточных узлов. Для каждой пары вершин (i, j) проверяется, сокращает ли путь через текущую промежуточную вершину k расстояние между i и j. Если это так, то Dj обновляется:

    [ Dj = \min(Dj, Dk + Dkj) ]

  3. Отсутствие отрицательных циклов. Если после выполнения алгоритма на диагонали матрицы D обнаружены отрицательные значения, то граф содержит отрицательный цикл.

Преимущества и недостатки

  • Преимущества: алгоритм прост в реализации, его сложность составляет O(n3), где n — количество вершин в графе. Он подходит для плотных графов.
  • Недостатки: неэффективен для разреженных графов из-за своей временной сложности и требует большой памяти.

Алгоритм Флойда-Уоршелла широко используется в задачах маршрутизации, таких как нахождение кратчайших путей в сетях связи и транспортных сетях.

Категория: Информатика

Теги: алгоритмы, программирование, графы, теоретическая информатика