Алгоритм Флойда — Уоршелла

Алгоритм Флойда — Уоршелла — это алгоритм на графах, предназначенный для нахождения кратчайших путей между всеми парами вершин во взвешенном ориентированном или неориентированном графе. Алгоритм работает с графами, содержащими рёбра с положительными, отрицательными весами, но без циклов отрицательного суммарного веса (отрицательных циклов). Он был опубликован Робертом Флойдом в 1962 году, хотя его основа была заложена Стивеном Уоршеллом в 1962 году для задачи транзитивного замыкания.

История

Алгоритм назван в честь двух американских учёных: Роберта Флойда и Стивена Уоршелла. В 1962 году Флойд опубликовал статью «Algorithm 97: Shortest Path», в которой описал метод нахождения кратчайших путей между всеми парами вершин. В том же году Уоршелл представил алгоритм для вычисления транзитивного замыкания бинарного отношения, который по своей структуре идентичен алгоритму Флойда. Позднее оба подхода были объединены под общим названием. Алгоритм является развитием идей динамического программирования и служит альтернативой многократному применению алгоритма Дейкстры (для графов с неотрицательными весами) или алгоритма Беллмана — Форда (для графов с отрицательными весами, но без отрицательных циклов).

Описание алгоритма

Основная идея

Алгоритм Флойда — Уоршелла основан на принципе динамического программирования. Он последовательно рассматривает каждую вершину графа в качестве промежуточной точки на пути между двумя другими вершинами. Если путь через эту промежуточную вершину оказывается короче текущего известного пути, то расстояние обновляется.

Пусть задан взвешенный граф с \( n \) вершинами, пронумерованными от 1 до \( n \). Алгоритм использует матрицу расстояний \( D \) размером \( n \times n \), где элемент \( D[i][j] \) равен весу ребра от вершины \( i \) к вершине \( j \). Если ребра нет, то \( D[i][j] \) устанавливается равным бесконечности (\( \infty \)). Для диагональных элементов \( D[i][i] \) обычно устанавливается 0.

Шаги алгоритма

1. Инициализация: заполнить матрицу \( D \) начальными весами рёбер.
2. Для каждой вершины \( k \) от 1 до \( n \):

• Для каждой пары вершин \( i \) и \( j \) от 1 до \( n \):
• Если \( D[i][k] + D[k][j] < D[i][j] \), то обновить \( D[i][j] = D[i][k] + D[k][j] \).

После завершения всех итераций матрица \( D \) содержит кратчайшие расстояния между всеми парами вершин. Если в графе есть отрицательный цикл, то на диагонали матрицы (элементы \( D[i][i] \)) появятся отрицательные значения, что является признаком его наличия.

Восстановление путей

Для восстановления самих кратчайших путей (не только длин) используется дополнительная матрица предков \( P \). Изначально \( P[i][j] = i \), если есть ребро от \( i \) к \( j \), иначе — специальное значение (например, -1). При обновлении расстояния \( D[i][j] \) через вершину \( k \) обновляется и \( P[i][j] = P[k][j] \). После завершения алгоритма путь от \( i \) к \( j \) восстанавливается рекурсивно: \( j \), затем \( P[i][j] \), затем \( P[i][P[i][j]] \) и так далее до \( i \).

Сложность

Временная сложность

Алгоритм Флойда — Уоршелла имеет временную сложность \( O(n^3) \), где \( n \) — количество вершин. Это связано с тремя вложенными циклами по всем вершинам. Для графов с большим числом вершин (например, \( n > 1000 \)) алгоритм становится неэффективным, и предпочтение отдаётся другим методам, таким как алгоритм Джонсона.

Пространственная сложность

Пространственная сложность составляет \( O(n^2) \) для хранения матрицы расстояний и, при необходимости, матрицы предков. Для очень больших графов это может быть проблемой, но для многих практических задач (например, в картографии с числом вершин до нескольких сотен) это приемлемо.

Применение

Транзитивное замыкание

Алгоритм Флойда — Уоршелла может быть адаптирован для вычисления транзитивного замыкания ориентированного графа. В этом случае вместо суммирования весов используется логическая операция ИЛИ, а вместо сравнения — логическое И. Матрица достижимости \( R \) обновляется по правилу: \( R[i][j] = R[i][j] \lor (R[i][k] \land R[k][j]) \). Этот вариант часто называют алгоритмом Уоршелла.

Поиск кратчайших путей в графах с отрицательными весами

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

Обнаружение отрицательных циклов

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

Решение задач оптимизации

Алгоритм применяется в различных областях, включая:

• Транспортные сети: расчёт кратчайших маршрутов между всеми парами городов.
• Компьютерные сети: поиск оптимальных путей передачи данных.
• Биоинформатика: анализ генетических последовательностей и метаболических путей.
• Игровая разработка: поиск путей для персонажей в игровых мирах.

Пример работы

Рассмотрим простой граф с 4 вершинами, где рёбра заданы следующими весами:

• 1 → 2: 3
• 1 → 3: 8
• 2 → 4: 1
• 3 → 2: 4
• 4 → 3: 2

Начальная матрица расстояний:

После выполнения алгоритма (итерации по \( k = 1, 2, 3, 4 \)) получаем:

Кратчайшее расстояние от 1 до 3 равно 6 (путь 1→2→4→3), а не 8, как было напрямую.

Критика и ограничения

Основным недостатком алгоритма является его высокая временная сложность \( O(n^3) \), что делает его непрактичным для графов с большим количеством вершин (например, более 10 000). Для разреженных графов (с малым числом рёбер) более эффективными могут быть алгоритмы, основанные на многократном применении алгоритма Дейкстры с использованием бинарной кучи (сложность \( O(n^2 \log n + n m) \), где \( m \) — число рёбер) или алгоритм Джонсона (\( O(n^2 \log n + n m) \)).

Кроме того, алгоритм требует хранения матрицы размером \( n \times n \), что при больших \( n \) приводит к значительным затратам памяти. Для графов с отрицательными циклами алгоритм не даёт корректного результата, а лишь сигнализирует об их наличии.

Интересные факты

• Алгоритм Флойда — Уоршелла является одним из первых примеров применения динамического программирования к задачам на графах.
• В 1962 году Флойд и Уоршелл опубликовали свои работы независимо друг от друга, но в одном и том же журнале Communications of the ACM.
• Алгоритм может быть легко распараллелен, так как каждая итерация по \( k \) может выполняться независимо для разных пар \( i, j \).

Источники

• Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.
• Warshall, S. (1962). A theorem on Boolean matrices. Journal of the ACM, 9(1), 11–12.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2005). Алгоритмы: построение и анализ. 2-е издание. М.: Вильямс.