Floyd-Warshall | kz-maxx

Флойд алгоритмі деген не?

Флойд-Уоршелл алгоритмі — барлық вершина жұптары арасындағы ең қысқа расстояние табатын алгоритм.

Дейкстра бір start вершинадан барлық вершинаға distance табады. Ал Флойд әр вершинадан әр вершинаға distance табады.

Флойд negative edge-пен жұмыс істей алады. Бірақ графта negative cycle болмауы керек.

Қашан қолданамыз?

барлық вершина жұптарының арасындағы distance керек болса
вершина саны аз болса, көбіне 400–500 дейін
граф ориентированный немесе неориентированный болуы мүмкін
negative edge болуы мүмкін
көп distance query болса

Егер вершина өте көп болса, мысалы 100000, Флойд жарамайды. Себебі оның уақыты O(n³).

Негізгі идея

Біз dist матрицасын сақтаймыз.

dist[i][j]

Бұл i вершинасынан j вершинасына дейінгі shortest distance.

Басында:

dist[i][i] = 0
dist[a][b] = a → b ребросының весі
егер path жоқ болса, 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 — start вершина
j — finish вершина

Маңызды: 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: барлық shortest distance

Ориентированный weighted graph берілген. Барлық вершина жұптары арасындағы shortest distance матрицасын шығару керек.

Input

Output

Егер path жоқ болса, -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 path жоқ болса, онда i → k → j path та жоқ.

Бұл тағы INF + сан қосқанда overflow болудан сақтайды.

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

Егер граф неориентированный болса, ребро екі жаққа жүреді.

Ребро:

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

Көп query

Кейде Флойдтан кейін көп сұрақ беріледі:

q query
әр query: a b
a-дан b-ға shortest distance шығару керек

Алдымен Флойдты бір рет жүргіземіз. Кейін әр query-ға O(1) уақытта жауап береміз:

cout << dist[a][b];

Задача 2: distance query

Граф және q query берілген. Әр query үшін екі вершина арасындағы shortest distance шығару керек.

Input

Output

8
7
-1

Query-пен реализация

#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;
}

Path қалпына келтіру

Флойд distance ғана емес, path-тың өзін де таба алады. Ол үшін nxt матрицасы керек.

int nxt[N][N];

nxt[i][j] — i-ден j-ға бара жатқанда i-ден кейінгі келесі вершина.

nxt инициализациясы

Егер a → b ребросы бар болса, онда a-дан кейінгі вершина — b.

nxt[a][b] = b;

Егер path-ты k арқылы жақсартсақ:

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

Себебі i-ден j-ға бару үшін алдымен i-ден k-ға барғандай жүреміз.

Path алу функциясы

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;
}

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;
}

Negative cycle

Negative cycle — вес суммасы нөлден кіші болатын цикл.

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

Егер осындай циклмен айнала беруге болса, shortest path мағынасыз болады. Себебі distance-ты шексіз азайта беруге болады.

Negative cycle қалай табылады?

Флойдтан кейін diagonal тексереміз:

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

Егер dist[i][i] < 0 болса, онда i вершинасынан reachable negative cycle бар.

Floyd vs Dijkstra

Алгоритм	Не табады	Уақыт	Қашан ыңғайлы
Dijkstra	бір вершинадан барлық вершинаға	O((n + m) log n)	вершина көп, вес теріс емес
Floyd	барлық жұп вершина арасында	O(n³)	вершина аз, query көп

Асимптотика

Параметр	Мәні
Уақыт	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]);
        }
    }
}