Bellman-Ford | kz-maxx

Bellman-Ford деген не?

Беллман-Форд алгоритмі — бір start вершинадан барлық басқа вершинаға дейінгі ең қысқа distance табатын алгоритм.

Дейкстрадан басты айырмашылығы: Bellman-Ford negative edge-пен жұмыс істей алады.

Егер графта negative weight болса, бірақ negative cycle болмаса, Bellman-Ford дұрыс shortest distance табады.

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

графта negative edge болса
бір вершинадан барлық вершинаға shortest distance керек болса
negative cycle бар ма тексеру керек болса
shortest path қалпына келтіру керек болса
вершина мен ребро саны өте үлкен болмаса

Егер барлық weight теріс емес болса, көбіне Дейкстра қолданған жақсы. Себебі Дейкстра жылдамырақ.

Негізгі идея

Дейкстрадағы сияқты біз distance массивін сақтаймыз:

dist[v]

Бұл start вершинадан v вершинасына дейінгі ең қысқа distance.

Басында:

dist[start] = 0
dist[қалғандары] = INF

Кейін барлық ребро бойынша бірнеше рет жүріп, distance-тарды жақсартамыз.

егер dist[a] + w < dist[b]
онда b-ға a арқылы бару жақсырақ
dist[b] жаңартамыз

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

Реброларды қалай сақтаймыз?

Bellman-Ford-та графты adjacency list емес, барлық ребролар массиві ретінде сақтау ыңғайлы.

struct Edge {
    int a;
    int b;
    int w;
};

vector<Edge> edges;

Мұнда:

a — ребро қайдан шығады
b — ребро қайда барады
w — реброның weight-і

Мысалы ребро:

1 → 2 weight 5

Былай қосамыз:

edges.push_back({1, 2, 5});

Relaxation деген не?

Relaxation — бір ребро арқылы distance-ты жақсарту әрекеті.

Мынадай ребро болсын:

a → b weight w

Егер a вершинасына дейін path бар болса, онда b вершинасын жақсартып көреміз:

if (dist[a] != INF && dist[a] + w < dist[b]) {
    dist[b] = dist[a] + w;
}

dist[a] != INF тексеруі керек. Себебі a-ға path жоқ болса, a арқылы b-ға бара алмаймыз.

Неге n - 1 рет жүреміз?

n вершинасы бар графта қарапайым shortest path максимум n - 1 ребродан тұрады.

Сондықтан барлық ребро бойынша n - 1 рет өту жеткілікті.

1-ші проход: 1 реброға дейінгі path жақсарады
2-ші проход: 2 реброға дейінгі path жақсарады
3-ші проход: 3 реброға дейінгі path жақсарады
...
n - 1 проход: барлық normal shortest path табылады

Базалық Bellman-Ford функциясы

void bellmanFord(int start) {
    dist[start] = 0;

    for (int i = 1; i <= n - 1; i++) {
        for (Edge e : edges) {
            int a = e.a;
            int b = e.b;
            int w = e.w;

            if (dist[a] != INF && dist[a] + w < dist[b]) {
                dist[b] = dist[a] + w;
            }
        }
    }
}

Мысал

Мынадай граф болсын:

1 → 2 weight 4
1 → 3 weight 5
2 → 3 weight -2
3 → 4 weight 3

Start вершина: 1.

Shortest distance:

Вершина	1-ден distance
1	0
2	4
3	2
4	5

Неге 3-ке distance 2?

1 → 2 → 3
4 + (-2) = 2

Неге 4-ке distance 5?

1 → 2 → 3 → 4
4 + (-2) + 3 = 5

Задача 1: бір вершинадан distance

Ориентированный weighted graph берілген. s вершинасынан барлық вершинаға дейінгі shortest distance табу керек. Графта negative edge болуы мүмкін.

Input

Output

0 4 2 5

Формат:

n m s
a b w
a b w
...

Толық реализация

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

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

struct Edge {
    int a;
    int b;
    int w;
};

int n, m, s;
vector<Edge> edges;
long long dist[N];

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

    cin >> n >> m >> s;

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

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

        edges.push_back({a, b, w});
    }

    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        for (Edge e : edges) {
            if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
            }
        }
    }

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

    return 0;
}

Оптимизация: ештеңе өзгермесе

Кейде алгоритмді ертерек тоқтатуға болады. Егер бір проход кезінде ешқандай update болмаса, ары қарай ештеңе өзгермейді.

bool changed = false;

for (Edge e : edges) {
    if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
        dist[e.b] = dist[e.a] + e.w;
        changed = true;
    }
}

if (!changed) {
    break;
}

Оптимизациямен реализация

dist[s] = 0;

for (int i = 1; i <= n - 1; i++) {
    bool changed = false;

    for (Edge e : edges) {
        if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
            dist[e.b] = dist[e.a] + e.w;
            changed = true;
        }
    }

    if (!changed) {
        break;
    }
}

Negative cycle

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

1 → 2 weight 3
2 → 3 weight -5
3 → 1 weight 1
сумма = -1

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

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

n - 1 проходтан кейін барлық ребро бойынша тағы бір рет жүреміз.

Егер n-ші проходта distance әлі жақсара алса, онда negative cycle бар.

bool hasCycle = false;

for (Edge e : edges) {
    if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
        hasCycle = true;
    }
}

Бұл тек start вершинадан reachable negative cycle табады.

Задача 2: negative cycle тексеру

Ориентированный graph және start вершина s берілген. s-тен reachable negative cycle бар ма, соны тексеру керек.

Input

Output

YES

Negative cycle табу толық коды

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

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

struct Edge {
    int a;
    int b;
    int w;
};

int n, m, s;
vector<Edge> edges;
long long dist[N];

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

    cin >> n >> m >> s;

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

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

        edges.push_back({a, b, w});
    }

    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        for (Edge e : edges) {
            if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
            }
        }
    }

    bool hasCycle = false;

    for (Edge e : edges) {
        if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
            hasCycle = true;
        }
    }

    if (hasCycle) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    return 0;
}

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

Shortest path шығару үшін p массиві керек.

int p[N];

Біз b вершинасына distance жақсартқанда, қай вершинадан келгенімізді сақтаймыз:

p[e.b] = e.a;

Яғни:

b вершинасына a вершинасынан келдік

Задача 3: shortest path шығару

Граф, start s және finish t берілген. s-тен t-ға дейінгі shortest path шығару керек.

Input

Output

1 2 3 4

Path-пен толық реализация

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

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

struct Edge {
    int a;
    int b;
    int w;
};

int n, m, s, t;
vector<Edge> edges;
long long dist[N];
int p[N];

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

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

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        p[i] = -1;
    }

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

        edges.push_back({a, b, w});
    }

    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        bool changed = false;

        for (Edge e : edges) {
            if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
                p[e.b] = e.a;
                changed = true;
            }
        }

        if (!changed) {
            break;
        }
    }

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

    vector<int> path;

    for (int v = t; v != -1; v = p[v]) {
        path.push_back(v);
    }

    reverse(path.begin(), path.end());

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

    return 0;
}

Ориентированный және неориентированный граф

Егер граф orientированный болса, реброны бір рет қосамыз:

edges.push_back({a, b, w});

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

edges.push_back({a, b, w});
edges.push_back({b, a, w});

Bellman-Ford vs Dijkstra

Алгоритм	Weight	Уақыт	Қашан қолданамыз
Dijkstra	тек negative емес	O((n + m) log n)	жылдам shortest path
Bellman-Ford	negative болуы мүмкін	O(n · m)	negative edge, negative cycle

Bellman-Ford vs Floyd

Алгоритм	Не табады	Уақыт	Память
Bellman-Ford	бір вершинадан барлық вершинаға	O(n · m)	O(n + m)
Floyd	барлық жұп вершина арасында	O(n³)	O(n²)

Асимптотика

Параметр	Мәні
Уақыт	O(n · m)
Память	O(n + m)

Егер n және m үлкен болса, Bellman-Ford slow болуы мүмкін. Бірақ negative edge бар кезде өте пайдалы.

Қысқа шаблон

const long long INF = 4e18;

struct Edge {
    int a;
    int b;
    int w;
};

vector<Edge> edges;
long long dist[N];

void bellmanFord(int s) {
    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        bool changed = false;

        for (Edge e : edges) {
            if (dist[e.a] != INF && dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
                changed = true;
            }
        }

        if (!changed) {
            break;
        }
    }
}