Алгоритм

Алгоритм Флойда-Уоршелла используется для нахождения длины кратчайшего пути между всеми парами вершин во взвешенном графе за \(O(N^3)\).

В основе алгоритма лежит достаточно простое ДП: пусть \(dp[i][j][k]\) - длина кратчайшего пути между вершинами \(i\) и \(j\), проходящего только через промежуточные вершины \(\{0, 1, \ldots, k\}\) (\(i\) и \(j\) не считаются).

Научимся пересчитывать пути при увеличении k: пусть мы хотим улучшить длину пути между \(i\) и \(j\) при увеличении \(k\) на \(1\). У нас есть два варианта: не использовать вершину \(k + 1\) (тогда \(dp[i][j][k + 1] = dp[i][j][k]\)), или использовать, пройдя через неё. Утверждается, что кратчайший путь из \(i\) в \(k + 1\) в \(j\) получается объединением кратчайших путей из \(i\) в \(k + 1\) и из \(k + 1\) в \(j\) (используя промежуточные вершины до \(k\), так как \(k + 1\) уже не является промежуточной). Тогда \(dp[i][j][k + 1] = dp[i][k + 1][k] + dp[k + 1][j][k]\).

Сразу же попробуем сократить количество используемой памяти. Заметим, что для улучшения любого пути нам нужны только предыдущие значения длин путей для \(k - 1\). Можно просто откинуть последнее измерение (\(k\)) в массиве, приняв \(dp[i][j]\) - текущая минимальная длина пути из \(i\) в \(j\), которую мы постепенно улучшаем.

В качестве начальных значений для ДП, просто запишем, что кратчайший путь из каждой вершины в саму себя равен \(0\): \(dp[i][i] = 0\); кратчайший путь между двумя вершинами, между которыми есть ребро равен его длине: \(dp[i][j] = len(i, j)\); а кратчайший путь между всеми остальными парами вершин равен бесконечности: \(dp[i][j] = \infty\). Заметьте, что начальные значения не используют никаких промежуточных вершин, поэтому начинать работу алгоритма нужно с \(k = 0\).

Реализация

Для реализации нам не требуется хранить сам граф (в виде матрицы или списка смежности). Просто при вводе рёбер будем заполнять начальные значения ДП. Затем по очереди используем каждую вершину от \(0\) до \(N - 1\) для улучшения пути между всеми парами вершин.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;

int dp[1000][1000];

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INF;
        }
    }

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

    for (int i = 0; i < m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        u--, v--;
        dp[u][v] = dp[v][u] = len;
    }

    for (int k = 0; k < n; k++) {        //текущая вершина, используемая для улучшения
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }

    //Массив dp содержит длины кратчайших путей между всеми парами вершин
}

Поведение при наличии отрицательных циклов

В отличие от алгоритма Дейкстры, алгоритм Флойда-Уоршелла может корректно работать при наличии в графе рёбер с отрицательным весом. Для этого стоит немного изменить реализацию, добавив явную проверку на равенство длины пути бесконечности. Без неё в массиве могут появляться расстояния \(\infty - 1\), \(\infty - 2\), и т.д. Они могут вызвать проблемы при достаточно больших длинах рёбер, поэтому перепишем алгоритм следующим образом:

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][k] < INF && dp[k][j] < INF) {   //явная проверка
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
}

Однако существуют графы, в которых отрицательный вес имеют не простые пути, а циклы. Они лишают смысла задачу о нахождении кратчайшего пути, так как позволяют получать пути бесконечно малой длины. С помощью алгоритма Флойда-Уоршелла можно легко проверять в графе наличие таких циклов: если после окончания работы алгоритма существует вершина \(i\) такая, что \(dp[i][i] < 0\), то она входит в отрицательный цикл.