Теория и методология алгоритма Флойда — Уоршелла
Постановка задачи
Дан взвешенный ориентированный граф G(V, E), вершины которого пронумерованы от 1 до n. Вес ребра u→v равен ω(u,v), если ребро существует, и +∞ в противном случае. Требуется найти матрицу кратчайших расстояний d, где d[i][j] — длина кратчайшего пути из i в j, либо +∞, если j недостижима из i.
Идея алгоритма
Обозначим через d(i)uv длину кратчайшего пути между u и v, использующего в качестве промежуточных только вершины из множества {1..i}. Тогда справедливо рекуррентное соотношение:
d(i)uv = min( d(i−1)uv , d(i−1)ui + d(i−1)iv )
Если кратчайший путь из u в v, проходящий только через вершины {1..i}, использует вершину i, то он состоит из кратчайшего пути u→i и кратчайшего пути i→v. Иначе он совпадает с кратчайшим путём, использующим лишь вершины {1..i−1}. Перебирая вершины i = 1..n по очереди и пересчитывая все пары (u, v), после n шагов получаем итоговую матрицу кратчайших расстояний.
Псевдокод (в первом приближении)
Прямая реализация хранит трёхмерный массив d(i)[u][v] и работает за Θ(n³) времени, используя при этом Θ(n³) памяти:
d[0][u][v] = w[u][v]
for i in V:
for u in V:
for v in V:
d[i][u][v] = min(d[i-1][u][v], d[i-1][u][i] + d[i-1][i][v])Оптимизация памяти: окончательная версия
Можно избавиться от индекса i и использовать один двумерный массив d[u][v], обновляя его «на месте». Корректность обеспечивается инвариантом ρ(u,v) ≤ d[u][v] ≤ d(i)uv: значения в массиве никогда не занижают истинное расстояние и монотонно к нему сходятся. Такая реализация всё ещё работает за Θ(n³), но требует уже только Θ(n²) памяти.
Реализация на Python
INF = float('inf')
def floyd_warshall(graph):
n = len(graph)
d = [row[:] for row in graph] # копия матрицы весов
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return d
graph = [
[0, 1, 6, INF],
[INF, 0, 4, 1],
[INF, INF, 0, INF],
[INF, INF, 1, 0]
]
for row in floyd_warshall(graph):
print(row)Восстановление кратчайшего пути
Чтобы получить не только длину, но и сам путь, заводят дополнительный массив next, хранящий следующую вершину на кратчайшем пути из u в v:
def floyd_warshall_with_path(graph, nxt):
n = len(graph)
d = [row[:] for row in graph]
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
nxt[i][j] = nxt[i][k]
return d, nxt
def get_path(u, v, d, nxt):
if d[u][v] == INF:
return None # пути между u и v нет
path = [u]
while u != v:
u = nxt[u][v]
path.append(u)
return pathПоиск отрицательного цикла
Если в графе есть цикл отрицательного веса, после завершения алгоритма на главной диагонали матрицы d появится хотя бы одно отрицательное число: d[i][i] < 0 означает, что через вершину i проходит цикл суммарно отрицательного веса. Чтобы не допустить переполнения при экспоненциальном уменьшении расстояний, значения дополнительно ограничивают снизу величиной −∞.
Построение транзитивного замыкания
Та же схема применима для отношений: если W[i][j] = 1 означает наличие ребра, то после выполнения W[i][j] = W[i][j] or (W[i][k] and W[k][j]) для всех троек i, j, k матрица W превращается в транзитивное замыкание отношения — W[i][j] = 1 тогда и только тогда, когда из i в j существует путь. Строки W можно упаковать в битовые маски, ускоряя внутренний цикл в 32 или 64 раза.
Сложность и ограничения
- Время работы: Θ(n³) независимо от числа рёбер — алгоритм невыгоден для разреженных графов, где n одиночных запусков Дейкстры могут оказаться быстрее.
- Память: Θ(n²) в оптимизированной версии.
- Корректно работает с отрицательными весами рёбер, но не с отрицательными циклами — при их наличии он позволяет их обнаружить, а не корректно посчитать расстояния.
- Константа в Θ(n³) очень мала — используются только сложение и сравнение, поэтому на практике алгоритм проще и часто быстрее асимптотически более сложных методов при небольших n.