Алгоритм Флойда-Уоршелла: что это и где он полезен

​​Алгоритм Флойда-Уоршелла — это мощный инструмент для поиска кратчайших путей в графе. Он может пригодиться в самых разных задачах. Разбираемся в теме подробно с Александром Рыжковым, ментором SF, руководителем команды LightAutoML и Kaggle Grandmaster.

Что такое алгоритм Флойда-Уоршелла?

Свое название алгоритм Флойда-Уоршелла получил благодаря двум ученым-информатикам, которые независимо друг от друга опубликовали его в 1962 году, — Роберту Флойду и Стивену Уоршеллу. 

Интересно, что за три года до этого, в 1959 году, схожий метод представил другой ученый, Бернард Рой, но его работа не привлекла широкого внимания научного сообщества. Почему-то именно статьи Флойда и Уоршелла стали основой для широкого распространения и признания этого алгоритма в области теории графов и компьютерных наук. 

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

Что такое динамическое программирование?

Прежде чем углубляться в детали алгоритма Флойда-Уоршелла, важно сказать о динамическом программировании (ДП).

ДП — это стратегия «Разделяй и властвуй», но с хитростью. Вместо того чтобы решать одну большую задачу, ее разбивают на более мелкие простые подзадачи. Затем решают эти подзадачи и сохраняют их результаты. Когда снова понадобится решение такой же подзадачи, можно просто взять готовый результат, вместо того чтобы считать заново.

Динамическое программирование и структура кратчайшего пути

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

Описание алгоритма Флойда-Уоршелла в виде псевдокода

Вот как выглядит алгоритм Флойда-Уоршелла в виде псевдокода:

function floydWarshall(graph):
  n = количество вершин в графе
  dist = матрица расстояний, изначально заполненная весами ребер (или бесконечностью, если ребра нет)
 
  for k from 0 to n-1:
for i from 0 to n-1:
  for j from 0 to n-1:
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
  return dist

Здесь graph — это граф, dist — матрица расстояний, а n — количество вершин. Проходим по всем вершинам k и для каждой пары вершин i и j проверяем, можно ли сделать путь из i в j короче, пройдя через k. Если да, то обновляем расстояние в матрице dist.

Почему это называется псевдокодом?

Пример кода на Python с использованием алгоритма Флойда-Уоршелла

Посмотрим, как это выглядит на Python. Вот простой пример реализации алгоритма Флойда-Уоршелла:

import numpy as np

def floyd_warshall(graph):
n = len(graph)
dist = np.array(graph, dtype=float) # Преобразуем в NumPy массив для удобства

 for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist

# Пример графа (матрица смежности)
graph = [
[0, 3, 8, np.inf, -4],
[np.inf, 0, np.inf, 1, 7],
[np.inf, 4, 0, np.inf, np.inf],
[2, np.inf, -5, 0, np.inf],
[np.inf, np.inf, np.inf, 6, 0]
]

shortest_paths = floyd_warshall(graph)
print("Матрица кратчайших расстояний:")
print(shortest_paths)

В этом примере мы используем NumPy для удобства работы с матрицами. Мы представляем граф в виде матрицы смежности, где float(‘inf’) обозначает отсутствие ребра. Функция floyd_warshall возвращает матрицу кратчайших расстояний между всеми парами вершин.

Оценки алгоритма Флойда-Уоршелла по времени работы и использованию памяти

Время работы

Алгоритм Флойда-Уоршелла имеет временную сложность O(n³), где n — количество вершин в графе. Почему так? Есть три вложенных цикла: один цикл k, который перебирает все вершины, и два цикла i и j, которые перебирают все пары вершин. Таким образом, общее количество операций пропорционально

n * n * n = n³. 

Это означает, что время работы алгоритма растет кубически с увеличением количества вершин. Если в графе 10 вершин, то время работы будет примерно в 1000 раз больше, чем для графа с одной вершиной. Если 100 вершин — то в миллион.

Использование памяти

Алгоритм использует дополнительную память для хранения матрицы расстояний dist. Размер этой матрицы равен n * n, поэтому пространственная сложность алгоритма составляет O(n²). Это означает, что объем памяти, необходимый для работы алгоритма, растет квадратично с увеличением количества вершин. Это, как правило, не является проблемой для графов умеренного размера, но может стать ограничением для очень больших графов.

Как работает алгоритм Флойда-Уоршелла для случая наличия отрицательных циклов в графе?

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

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

Почему так? Если есть отрицательный цикл, то можно, пройдя по нему, вернуться в ту же вершину, но с меньшим расстоянием, чем было изначально. Это и отражается в отрицательном значении на диагонали.

Практические примеры использования алгоритма Флойда-Уоршелла

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

Навигационные системы

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

Анализ социальных сетей

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

Транспортная логистика

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

Сетевые протоколы

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

Биоинформатика

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

Игры

В играх, особенно в стратегиях, алгоритм Флойда-Уоршелла используется для поиска кратчайших путей для юнитов, а также для анализа игровой карты. Например, если вы играете в стратегию, где юниты должны перемещаться по карте, этот алгоритм может помочь найти оптимальные пути для их перемещения.

Коротко об алгоритме Флойда-Уоршелла

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