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

Принцип Флойда-Уоршелла

Алгоритм Флойда-Уоршелла — классический алгоритм нахождения кратчайших путей между ВСЕМИ парами вершин в графе. Использует динамическое программирование.

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

Идея: dist[i][k] — длина кратчайшего пути от i до j, использующего только вершины {1..k} как промежуточные. На каждой итерации k увеличивается допустимое множество промежуточных вершин.

Псевдокод

function FloydWarshall(graph): n = number of vertices dist = copy of adjacency matrix next = matrix initialized as: next[i][j] = j for k = 1 to n: for i = 1 to n: for j = 1 to n: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] next[i][j] = next[i][k] return dist, next

Когда применять Флойд-Уоршелл

• Все пары вершин нужны одновременно: вместо V × Дейкстра — один Флойд.
• Плотный граф: E ≈ V². Сложность Флойда O(V³) = O(V·E), а Дейкстры × V = O(V·E·log V) — Флойд быстрее на log V.
• Отрицательные веса: Дейкстра не работает, Флойд — да.
• Поиск отрицательного цикла: после алгоритма проверьте dist[i][i] < 0.
• Транзитивное замыкание: алгоритм Уоршелла — частный случай для булевых матриц.

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

Матрица dist даёт только длины путей. Чтобы получить сам путь, нужна вторая матрица next:

• next[i][j] = следующая вершина после i на пути i → j.
• Изначально: next[i][j] = j для всех рёбер (i,j).
• При обновлении: если dist[i][k] + dist[k][j] < dist[i][j], то next[i][j] = next[i][k].
• Восстановление пути от u до v: u → next[u][v] → next[next[u][v]][v] → ... → v.