Bellman-Ford | kz-maxx

Что такое Bellman-Ford?

Алгоритм Беллмана-Форда — это алгоритм для поиска кратчайших расстояний от одной стартовой вершины до всех остальных вершин.

Главное отличие от Дейкстры: Bellman-Ford может работать с отрицательными ребрами.

Если в графе есть отрицательные веса, но нет отрицательного цикла, Bellman-Ford найдет правильные кратчайшие расстояния.

Когда использовать?

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

Если все веса неотрицательные, чаще лучше использовать Дейкстру, потому что она работает быстрее.

Главная идея

Как и в Дейкстре, мы храним массив расстояний:

dist[v]

Это минимальное расстояние от стартовой вершины до вершины v.

В начале:

dist[start] = 0
dist[остальные] = INF

Потом мы много раз проходим по всем ребрам и пытаемся улучшить расстояния.

если dist[a] + w < dist[b]
значит путь до b через a лучше
обновляем dist[b]

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

Как хранить ребра?

В Bellman-Ford удобнее хранить граф не через список смежности, а просто массив всех ребер.

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

vector<Edge> edges;

Здесь:

a — откуда идет ребро
b — куда идет ребро
w — вес ребра

Например ребро:

1 → 2 вес 5

Добавляем так:

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

Что такое relaxation?

Relaxation — это попытка улучшить расстояние по одному ребру.

Пусть есть ребро:

a → b вес w

Если до a мы уже умеем дойти, то можно попробовать улучшить b:

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

Проверка dist[a] != INF нужна, потому что если до a пути нет, то через a тоже идти нельзя.

Почему делаем n - 1 проход?

В графе с n вершинами простой кратчайший путь содержит максимум n - 1 ребро.

Поэтому достаточно n - 1 раз пройти по всем ребрам.

1-й проход улучшает пути длиной до 1 ребра
2-й проход улучшает пути длиной до 2 ребер
3-й проход улучшает пути длиной до 3 ребер
...
n - 1 проход улучшает все нормальные кратчайшие пути

Базовая функция 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 вес 4
1 → 3 вес 5
2 → 3 вес -2
3 → 4 вес 3

Стартовая вершина: 1.

Кратчайшие расстояния:

Вершина	Расстояние от 1
1	0
2	4
3	2
4	5

Почему до 3 расстояние 2?

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

Почему до 4 расстояние 5?

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

Задача 1: расстояния от одной вершины

Дан ориентированный взвешенный граф. Нужно найти кратчайшие расстояния от вершины s до всех вершин. В графе могут быть отрицательные ребра.

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

Оптимизация: если ничего не изменилось

Иногда можно закончить раньше. Если за один проход по всем ребрам не было обновлений, значит дальше ничего не изменится.

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

Отрицательный цикл

Отрицательный цикл — это цикл, сумма весов которого меньше нуля.

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

Если можно попасть в такой цикл, то кратчайший путь может не существовать. Мы можем крутиться по циклу и уменьшать расстояние бесконечно.

Как найти отрицательный цикл?

После n - 1 проходов делаем еще один проход по всем ребрам.

Если на n-м проходе расстояние всё еще можно улучшить, значит есть отрицательный цикл.

bool hasCycle = false;

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

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

Задача 2: проверить отрицательный цикл

Дан ориентированный граф и стартовая вершина s. Нужно проверить, есть ли отрицательный цикл, достижимый из s.

Input

Output

YES

Полная реализация поиска отрицательного цикла

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

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

Чтобы восстановить кратчайший путь, нужен массив p.

int p[N];

Когда мы улучшаем расстояние до b, запоминаем вершину a:

p[e.b] = e.a;

То есть:

в вершину b мы пришли из вершины a

Задача 3: вывести кратчайший путь

Дан граф, старт s и финиш t. Нужно вывести кратчайший путь из s в t.

Input

Output

1 2 3 4

Полная реализация с путем

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

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

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

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

Если граф неориентированный, ребро идет в обе стороны:

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

Bellman-Ford vs Dijkstra

Алгоритм	Веса	Время	Когда использовать
Dijkstra	только неотрицательные	O((n + m) log n)	быстрые кратчайшие пути
Bellman-Ford	можно отрицательные	O(n · m)	negative edges, 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 может работать медленно. Но он полезен, когда есть отрицательные ребра.

Короткий шаблон

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