Алгоритм Флойда-Уоршелла для нахождения кратчайших путей

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

Основная идея алгоритма Флойда

Основная идея алгоритма Флойда заключается в следующем:

1. Задается граф G с весами ребер
2. Строится матрица кратчайших расстояний между всеми парами вершин
3. Последовательно каждая вершина рассматривается как промежуточная
4. Для каждой пары вершин (i, j) проверяется, уменьшится ли расстояние между ними, если добавить текущую промежуточную вершину k
5. Если да, то обновляется матрица кратчайших расстояний

Таким образом, на каждой итерации алгоритм пытается улучшить имеющиеся маршруты за счет добавления новой "пересадочной" вершины. После рассмотрения всех вершин в качестве промежуточных, в матрице кратчайших расстояний будут записаны длины оптимальных путей.

Алгоритм Флойда для обнаружения отрицательных циклов

Алгоритм Флойда может быть также использован для обнаружения отрицательных циклов в графе. Как это работает? На каждой итерации алгоритма для каждой вершины i проверяется, не уменьшится ли расстояние от этой вершины до самой себя при проходе через текущую промежуточную вершину k. Если да, значит найден путь от i до i через k, имеющий отрицательный вес. А это и есть отрицательный цикл!

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

Код алгоритма Флойда на Python

Реализация алгоритма Флойда на языке Python выглядит следующим образом:

 def floyd_warshall(graph): dist = deepcopy(graph) for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) return dist 

Здесь graph - это матрица смежности исходного графа, а dist - матрица кратчайших расстояний, которая заполняется в процессе работы алгоритма.

Ключевые моменты:

• Внешний цикл по k - промежуточная вершина
• Во внутренних циклах рассматривается каждая пара вершин i и j
• Вычисляется расстояние через k и сравнивается с имеющимся расстоянием без k
• Записывается минимальное из двух значений

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

Временная сложность алгоритма Флойда составляет O(V^3), где V - число вершин в графе. Это обусловлено тремя вложенными циклами по вершинам.

Пространственная сложность также равна O(V^2) и определяется размером матрицы кратчайших расстояний.

Таким образом, на практике алгоритм применим для графов с небольшим количеством вершин (сотни или тысячи). При большем числе вершин требуемые ресурсы быстро возрастают.

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

Хотя чаще используется название "алгоритм Флойда", иногда можно встретить и другие варианты, например "алгоритм Флойда — Уоршелла". Это связано с тем, что данный метод был предложен несколькими учеными практически одновременно.

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

Поэтому часто используется двойное название "Флойд — Уоршелл" или "Флойд — Уоршелл — Рой", чтобы отдать должное всем авторам.

Пример работы алгоритма Флойда

Рассмотрим работу алгоритма Флойда на простом примере:

Это матрица смежности графа с 3 вершинами. Например, ребро от вершины 1 к 3 имеет вес 8.

После первой итерации алгоритма (k = 1) матрица кратчайших путей будет выглядеть так:

Обратите внимание, как уменьшилось расстояние от вершины 2 до 3 (с 8 до 5) за счет прохода через промежуточную вершину 1.

После второй итерации (k = 2):

Здесь уменьшилось расстояние от 3 до 2, опять же за счет использования промежуточной вершины (1).

Так как вершин всего 3, то на следующей итерации алгоритм закончит работу. Итоговая матрица кратчайших путей будет выглядеть так же, как и после второй итерации.

Как видно на этом простом примере, алгоритм Флойда позволяет эффективно находить оптимальные маршруты между всеми парами вершин графа за полиномиальное время.

Учет отрицательных ребер и циклов

Рассмотренный выше алгоритм Флойда работает корректно, только если в графе отсутствуют отрицательные циклы. Что если такие циклы есть? В этом случае некоторые расстояния могут уменьшаться бесконечно.

Однако алгоритм Флойда позволяет не только найти сами отрицательные циклы, но и вычислить кратчайшие расстояния в графе с отрицательными ребрами.

Поиск отрицательных циклов

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

Для этого достаточно для каждой вершины i проверить dist[i][i]. Если оно меньше 0, значит найден цикл через i. Далее, восстанавливая предыдущие вершины из массива next, можно получить этот цикл целиком.

Учет отрицательных ребер

При наличии отрицательных ребер, алгоритм Флойда также может быть применен. Однако требуется внести небольшие коррективы:

1. Задать бесконечно большое число для обозначения "отсутствия пути" вместо -1
2. Сравнивать с этим числом вместо проверки на минимум
3. Инициализировать матрицу расстояний исходными весами ребер

При такой модификации алгоритм снова будет работать верно, находя оптимальные пути и при наличии отрицательных ребер (но не циклов!).

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

Как уже было сказано, на основе заполненных матриц dist и next можно не только найти длину кратчайшего пути между любой парой вершин, но и восстановить этот путь полностью.

Алгоритм заключается в следующем:

1. Задать конечную и начальную вершины - i и j
2. Добавить i в начало пути path
3. Получить из next[i] следующую вершину после i
4. Если это j - завершить алгоритм
5. Иначе добавить новую вершину в начало path и вернуться к п.3

В результате в массиве path будет записан кратчайший путь от i до j.

Ускорение алгоритма Флойда

Несмотря на простоту и наглядность, асимптотическая сложность алгоритма Флойда довольно высока. Существуют различные методы для его ускорения в практических приложениях:

• Использование матричного перемножения
• Распараллеливание внешнего и внутренних циклов
• Применение эвристик для оптимизации порядка вершин
• Кэширование промежуточных результатов

Однако асимптотика остается прежней - O(V^3). Поэтому при очень больших графах требуются другие алгоритмы.