13.3 Алгоритм Флойда–Уоршелла¶

Введение¶

Алгоритм Флойда–Уоршелла — это классический метод для поиска кратчайших путей между всеми парами вершин в графе.

В отличие от алгоритма Дейкстры, который ищет кратчайшие пути от одной вершины, здесь мы сразу получаем расстояния между всеми вершинами.

Алгоритм работает для ориентированных и неориентированных графов и допускает отрицательные веса рёбер (но не допускает отрицательных циклов).

Интуиция¶

Главная идея алгоритма — постепенно улучшать расстояния между всеми парами вершин, разрешая использовать всё больше промежуточных вершин.

Пусть у нас есть вершины 1..n.

Обозначим:

d[i][j] — кратчайшее расстояние из i в j.

Сначала мы знаем только:

• прямые рёбра
• расстояние до себя (0)

Далее мы начинаем "разрешать" использовать промежуточные вершины.

Идея такая:

Можно ли улучшить путь i → j, если разрешить проход через вершину k?

Тогда:

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Основной переход¶

На каждом шаге мы выбираем промежуточную вершину k и обновляем все пары (i, j):

Если путь i → k → j короче текущего, то обновляем.

Таким образом:

1. Сначала разрешаем только вершину 1
2. Потом вершины {1,2}
3. Потом {1,2,3}
4. …

И в конце разрешены все вершины

Алгоритм¶

Три вложенных цикла:

1. выбираем промежуточную вершину k
2. перебираем начало i
3. перебираем конец j

Пример¶

Рассмотрим граф из 4 вершин:

mermaid

graph LR A((1)) -->|5| B((2)) B -->|3| C((3)) A -->|10| C C -->|1| D((4))

Изначально:

• d[1][3] = 10

Но есть путь: 1 → 2 → 3 = 5 + 3 = 8

После шага с k = 2 мы получим:

• d[1][3] = 8

Затем через вершину 3:

• d[1][4] = 8 + 1 = 9

Пошаговый разбор¶

Матрица расстояний изначально:

0   5  10  INF
INF 0   3  INF
INF INF 0   1
INF INF INF 0

0   5   8  INF
INF 0   3  INF
INF INF 0   1
INF INF INF 0

0   5   8   9
INF 0   3   4
INF INF 0   1
INF INF INF 0

Реализация на C++¶

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n, m;
cin >> n >> m;

const int INF = 1e9;

vector<vector<int>> d(n, vector<int>(n, INF));

for (int i = 0; i < n; i++) {
    d[i][i] = 0;
}

for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--; b--;
    d[a][b] = min(d[a][b], w);
}

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][k] < INF && d[k][j] < INF) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (d[i][j] == INF) cout << "INF ";
        else cout << d[i][j] << " ";
    }
    cout << '\n';
}
}

Сложность¶

Время работы:

O(n^3)

Память:

O(n^2)

Это делает алгоритм подходящим для n ≤ 500 (примерно).

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

После выполнения алгоритма:

Если d[i][i] < 0 хотя бы для одной вершины i — значит есть отрицательный цикл.

Когда использовать¶

Алгоритм Флойда–Уоршелла стоит применять, когда:

• нужно найти расстояния между всеми парами вершин
• граф небольшой (n до ~500)
• есть отрицательные веса
• требуется простая реализация

Когда НЕ использовать¶

• если n большой (лучше запускать Дейкстру несколько раз)
• если нужен путь только из одной вершины

Типичные ошибки¶

1. Переполнение

Если веса большие, используйте long long.

1. Отсутствие проверки INF

Нужно проверять, что путь существует перед сложением.

1. Неправильная инициализация

2. d[i][i] = 0 обязательно

3. остальные = INF

4. Забыли про кратные рёбра

Нужно брать минимум при вводе.

Итог¶

Алгоритм Флойда–Уоршелла — простой и мощный инструмент для задач на кратчайшие пути между всеми вершинами.

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