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

      

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

Сложность алгоритма

Три вложенных цикла содержат операцию, исполняемую за константное время.

                                                                

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

Сравнение с другими алгоритмами

Алгоритм Флойда — Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. В случае разреженных графов с рёбрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет  при применении двоичной кучи, что лучше, чем  алгоритма Флойда — Уоршелла тогда, когда  существенно меньше  (условие плотности графа). Если граф разрежен, у него имеются рёбра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

Также являются известными алгоритмы с применением алгоритмов быстрого перемножения матриц, которые ускоряют вычисления в плотных графах, но они обычно имеют дополнительные ограничения (например, представление весов рёбер в виде малых целых чисел). Вместе с тем, из-за большого константного фактора времени выполнения преимущество при вычислениях над алгоритмом Флойда — Уоршелла проявляется только на больших графах.

Реализация

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

Затем по очереди используем каждую вершину от 00 до N−1 N−1 для улучшения пути между всеми парами вершин.

#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 содержит длины кратчайших путей между всеми парами вершин}

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

В отличие от алгоритма Дейкстры, алгоритм Флойда-Уоршелла может корректно работать при наличии в графе рёбер с отрицательным весом. Для этого стоит немного изменить реализацию, добавив явную проверку на равенство длины пути бесконечности. Без неё в массиве могут появляться расстояния ∞−1 ∞−1, ∞−2, ∞−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]);
            }
        }
    }
}

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