Floyd-Warshall | kz-maxx

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

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

Если Дейкстра ищет расстояния от одной вершины, то Флойд ищет расстояния сразу от каждой вершины до каждой.

Флойд работает с отрицательными ребрами, но не должен быть отрицательный цикл.

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

нужно расстояние между всеми парами вершин
вершин мало, обычно до 400–500
граф может быть ориентированный или неориентированный
могут быть отрицательные ребра
нужно быстро отвечать на много запросов расстояния

Если вершин много, например 100000, Флойд не подойдет. У него время O(n³).

Главная идея

Мы храним матрицу dist.

dist[i][j]

Это кратчайшее расстояние из вершины i в вершину j.

В начале:

dist[i][i] = 0
dist[a][b] = вес ребра a → b
если пути нет, dist[i][j] = INF

Основная формула

Пусть мы хотим улучшить путь из i в j. Попробуем пройти через вершину k.

i → k → j

Если путь через k короче, то обновляем:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Это главная формула алгоритма Флойда.

Почему три цикла?

В алгоритме есть три цикла:

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

Смысл:

k — вершина, через которую пробуем пройти
i — стартовая вершина
j — конечная вершина

Важно: цикл по k должен быть самым внешним.

Пример

Пусть есть граф:

1 → 2 вес 5
1 → 3 вес 10
2 → 3 вес 2

Сначала:

dist[1][3] = 10

Но если пройти через 2:

1 → 2 → 3
5 + 2 = 7

Новый путь лучше:

dist[1][3] = 7

Задача 1: все кратчайшие расстояния

Дан ориентированный взвешенный граф. Нужно вывести матрицу кратчайших расстояний между всеми парами вершин.

Input

Output

Если пути нет, выводим -1.

Полная реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const long long INF = 4e18;

int n, m;
long long dist[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        dist[a][b] = min(dist[a][b], 1LL * w);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) {
                    continue;
                }

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF) {
                cout << -1 << ' ';
            } else {
                cout << dist[i][j] << ' ';
            }
        }

        cout << '\n';
    }

    return 0;
}

Почему проверяем INF?

Перед обновлением лучше проверять:

if (dist[i][k] == INF || dist[k][j] == INF) {
    continue;
}

Потому что если пути i → k или k → j нет, то путь i → k → j тоже невозможен.

Еще это защищает от переполнения, когда мы складываем INF + число.

Неориентированный граф

Если граф неориентированный, то ребро идет в обе стороны.

Для ребра:

a -- b вес w

Нужно добавить:

dist[a][b] = min(dist[a][b], 1LL * w);
dist[b][a] = min(dist[b][a], 1LL * w);

Если граф ориентированный, добавляем только:

dist[a][b] = min(dist[a][b], 1LL * w);

Много запросов

Иногда после построения кратчайших расстояний дают много запросов:

q запросов
каждый запрос: a b
нужно вывести кратчайшее расстояние из a в b

Сначала один раз запускаем Флойда. Потом каждый запрос отвечаем за O(1):

cout << dist[a][b];

Задача 2: запросы расстояний

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

Input

Output

8
7
-1

Реализация с запросами

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const long long INF = 4e18;

int n, m, q;
long long dist[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        dist[a][b] = min(dist[a][b], 1LL * w);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) {
                    continue;
                }

                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    while (q--) {
        int a, b;
        cin >> a >> b;

        if (dist[a][b] == INF) {
            cout << -1 << '\n';
        } else {
            cout << dist[a][b] << '\n';
        }
    }

    return 0;
}

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

Флойд может находить не только расстояние, но и сам путь. Для этого нужна матрица nxt.

int nxt[N][N];

nxt[i][j] — это следующая вершина после i, если мы идем из i в j.

Инициализация nxt

Когда есть ребро a → b, то следующая вершина после a — это b.

nxt[a][b] = b;

Если улучшаем путь через k, то:

nxt[i][j] = nxt[i][k];

Потому что из i в j сначала надо идти так же, как из i в k.

Функция получения пути

vector<int> getPath(int a, int b) {
    vector<int> path;

    if (nxt[a][b] == -1) {
        return path;
    }

    path.push_back(a);

    while (a != b) {
        a = nxt[a][b];
        path.push_back(a);
    }

    return path;
}

Полная реализация с восстановлением пути

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const long long INF = 4e18;

int n, m, s, t;
long long dist[N][N];
int nxt[N][N];

vector<int> getPath(int a, int b) {
    vector<int> path;

    if (nxt[a][b] == -1) {
        return path;
    }

    path.push_back(a);

    while (a != b) {
        a = nxt[a][b];
        path.push_back(a);
    }

    return path;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
                nxt[i][j] = i;
            } else {
                dist[i][j] = INF;
                nxt[i][j] = -1;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        if (w < dist[a][b]) {
            dist[a][b] = w;
            nxt[a][b] = b;
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) {
                    continue;
                }

                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    nxt[i][j] = nxt[i][k];
                }
            }
        }
    }

    if (dist[s][t] == INF) {
        cout << -1;
        return 0;
    }

    vector<int> path = getPath(s, t);

    for (int x : path) {
        cout << x << ' ';
    }

    return 0;
}

Отрицательный цикл

Отрицательный цикл — это цикл, сумма весов которого меньше нуля.

1 → 2 вес 3
2 → 3 вес -5
3 → 1 вес 1
сумма = -1

Если можно крутиться по такому циклу, то кратчайший путь не имеет смысла, потому что расстояние можно уменьшать бесконечно.

Как найти отрицательный цикл?

После Флойда проверяем диагональ:

for (int i = 1; i <= n; i++) {
    if (dist[i][i] < 0) {
        cout << "NEGATIVE CYCLE";
    }
}

Если dist[i][i] < 0, значит есть отрицательный цикл, достижимый из вершины i.

Floyd vs Dijkstra

Алгоритм	Что ищет	Время	Когда удобно
Dijkstra	от одной вершины до всех	O((n + m) log n)	много вершин, веса неотрицательные
Floyd	между всеми парами	O(n³)	мало вершин, много запросов

Асимптотика

Параметр	Значение
Время	O(n³)
Память	O(n²)

Если n = 500, то примерно 125 миллионов операций. Это обычно еще нормально на C++.

Короткий шаблон

const long long INF = 4e18;

long long dist[N][N];

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) {
            dist[i][j] = 0;
        } else {
            dist[i][j] = INF;
        }
    }
}

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][k] == INF || dist[k][j] == INF) {
                continue;
            }

            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}