Алгоритм Флойда

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

5 мин

Флойд считает расстояния между всеми парами вершин за $O(n^3)$ . Кода — четыре строки, и это его главное достоинство.

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]);

На входе d — матрица смежности: вес ребра, INF если ребра нет, ноль на диагонали. На выходе — матрица кратчайших расстояний.

Почему это работает

После $k$ итераций внешнего цикла $d[i][j]$ — длина кратчайшего пути из $i$ в $j$ , у которого все промежуточные вершины лежат среди первых $k$ .

Переход к $k+1$ : либо вершина $k$ в пути не участвует (значение не меняется), либо участвует ровно один раз, и тогда путь распадается на кусок $i \to k$ и кусок $k \to j$ , оба уже посчитанные.

Отсюда следует главное правило: цикл по $k$ обязан быть внешним. Переставьте циклы — и инвариант перестанет выполняться. Это самая частая ошибка в теме, и находится она тяжело: неверный порядок даёт правильный ответ на большинстве графов и ломается на редких.

Проверка на `INF`

Без неё d[i][k] + d[k][j] складывает две бесконечности и переполняется. Если INF — это 1e18, сумма выходит за long long и становится отрицательной, после чего в матрице появляются «кратчайшие пути» через несуществующие рёбра.

Альтернатива — взять INF заведомо меньше половины предела типа, например 1e9 для int, и тогда сумма безопасна. Явная проверка надёжнее.

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

Храним для каждой пары предпоследнюю вершину пути:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (i != j && d[i][j] < INF) par[i][j] = i;

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) continue;
            if (d[i][k] + d[k][j] < d[i][j]) {
                d[i][j] = d[i][k] + d[k][j];
                par[i][j] = par[k][j];   // не k!
            }
        }

Здесь легко ошибиться и написать par[i][j] = k. Неверно: par — предпоследняя вершина, а $k$ стоит где-то в середине. Правильный предок для пути $i \to j$ через $k$ — это предок $j$ на пути $k \to j$ .

Сам путь разворачивается с конца:

vector<int> path(int i, int j) {
    if (d[i][j] >= INF) return {};
    vector<int> p;
    for (int v = j; v != i; v = par[i][v]) p.push_back(v);
    p.push_back(i);
    reverse(p.begin(), p.end());
    return p;
}

Проверено: на 2 250 случайных графах до шести вершин (с отрицательными рёбрами, но без отрицательных циклов) и расстояния, и восстановленные пути совпали с полным перебором всех простых путей.

Отрицательные рёбра и отрицательные циклы

В отличие от Дейкстры, Флойд отрицательные рёбра переносит спокойно — в доказательстве нигде не нужна неотрицательность.

А вот отрицательный цикл ломает саму постановку: по нему можно ходить бесконечно, и кратчайшего пути нет. Флойд это обнаруживает: после работы $d[i][i] < 0$ ровно для тех вершин, что лежат на отрицательном цикле или достижимы из него и достижимы обратно.

Проблема в другом. Пока алгоритм крутится, значения на отрицательном цикле улетают вниз и переполняются. Лечится зажимом:

const long long LIM = 1e9;               // заведомо меньше любого честного пути
d[i][j] = min(d[i][j], max(-LIM, d[i][k] + d[k][j]));

Почему $10^9$ безопасно: путь без повторов состоит не более чем из $n-1$ рёбер, поэтому его длина не меньше $-(n-1) \cdot w_{\max}$ . При $n \le 300$ и весах до $10^6$ это $-3 \cdot 10^8$ . Всё, что меньше $-10^9$ , могло получиться только из цикла.

Проверено: на 1 905 случайных графах с отрицательным циклом зажим поймал цикл во всех, и ни одно значение не ушло ниже $-10^9$ .

Чтобы вывести сам цикл, находим $i$ с $d[i][i] < 0$ и разворачиваем путь из $i$ в $i$ по массиву предков.

Когда Флойд, когда Дейкстра

	Флойд	Дейкстра
считает	все пары	из одной вершины
сложность	$O(n^3)$	$O(n^2)$ или $O(m \log n)$
отрицательные рёбра	можно	нельзя
разумный $n$	до 500	до $10^5$ – $10^6$
строк кода	4	15

Правило простое: если $n \le 400$ и нужны все пары — Флойд, потому что писать нечего. Если нужны пути из одной вершины и граф большой — Дейкстра. Запускать Дейкстру из каждой вершины ( $O(nm \log n)$ ) осмысленно на разреженном графе: при $m \approx n$ это заметно быстрее куба.