13. Кратчайшие пути¶

13.1 Алгоритм Беллмана–Форда¶

Алгоритм Беллмана–Форда ищет кратчайшие пути от одной стартовой вершины до всех остальных вершин графа.

Его главное достоинство в том, что он работает даже тогда, когда в графе есть отрицательные веса рёбер. Кроме того, с его помощью можно обнаружить отрицательный цикл.

Идея алгоритма¶

Пусть dist[v] — текущее лучшее известное расстояние от стартовой вершины s до вершины v.

В начале:

dist[s] = 0
для всех остальных вершин dist[v] = INF

Дальше мы много раз просматриваем все рёбра графа и пытаемся улучшить расстояния.

Если есть ребро из a в b веса w, то выполняем релаксацию:

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

Идея простая: если мы уже умеем добираться до a, то, возможно, путь до b через a окажется лучше текущего.

Почему достаточно `n-1` проходов¶

Если в графе n вершин, то любой простой путь содержит не более n-1 ребра.

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

Схема работы¶

graph LR
    S[Стартовая вершина s] --> I["dist[s] = 0"]
    I --> A[Остальным вершинам INF]
    A --> B[Повторить n-1 раз]
    B --> C[Просмотреть все ребра]
    C --> D[Пробовать улучшать расстояния]
    D --> E[Получить кратчайшие пути]

Hold "Ctrl" to enable pan & zoom

Пример¶

Рассмотрим ориентированный граф:

graph LR
    1 -->|5| 2
    1 -->|3| 3
    2 -->|2| 5
    3 -->|1| 4
    4 -->|2| 5
    2 -->|3| 4

Hold "Ctrl" to enable pan & zoom

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

Начало¶

dist[1] = 0
dist[2] = INF
dist[3] = INF
dist[4] = INF
dist[5] = INF

После первого прохода¶

Из вершины 1 сразу улучшаются расстояния:

dist[2] = 5
dist[3] = 3

Затем из вершины 3:

dist[4] = 4

Затем из вершины 4:

dist[5] = 6

Также путь 1 → 2 → 5 даёт расстояние 7, но это хуже, чем 6.

Итого:

dist[1] = 0
dist[2] = 5
dist[3] = 3
dist[4] = 4
dist[5] = 6

На следующих проходах улучшений уже не будет.

Кратчайший путь до вершины 5 — это:

graph LR
    1 -->|3| 3
    3 -->|1| 4
    4 -->|2| 5

Hold "Ctrl" to enable pan & zoom

Его длина равна 6.

Реализация на C++¶

Обычно алгоритм удобно писать через список рёбер.

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

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

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

    int n, m, s;
    cin >> n >> m >> s;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        bool changed = false;
        for (auto e : edges) {
            if (dist[e.a] == INF) continue;
            if (dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
                changed = true;
            }
        }
        if (!changed) break;
    }

    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) cout << "INF\n";
        else cout << dist[v] << "\n";
    }

    return 0;
}

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

Если нужно не только расстояние, но и сам путь, можно хранить массив предков parent.

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

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

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

    int n, m, s, f;
    cin >> n >> m >> s >> f;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    vector<int> parent(n + 1, -1);

    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        bool changed = false;
        for (auto e : edges) {
            if (dist[e.a] == INF) continue;
            if (dist[e.a] + e.w < dist[e.b]) {
                dist[e.b] = dist[e.a] + e.w;
                parent[e.b] = e.a;
                changed = true;
            }
        }
        if (!changed) break;
    }

    if (dist[f] == INF) {
        cout << "Пути нет\n";
        return 0;
    }

    cout << "Длина: " << dist[f] << "\n";

    vector<int> path;
    int cur = f;
    while (cur != -1) {
        path.push_back(cur);
        cur = parent[cur];
    }
    reverse(path.begin(), path.end());

    for (int v : path) {
        cout << v << ' ';
    }
    cout << "\n";

    return 0;
}

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

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

Почему? Потому что по такому циклу можно пройти ещё раз и сделать путь ещё короче. Потом ещё раз — и ещё короче.

Пример:

graph LR
    2 -->|1| 3
    3 -->|-7| 4
    4 -->|2| 2

Hold "Ctrl" to enable pan & zoom

Сумма весов цикла:

1 + (-7) + 2 = -4

Это отрицательный цикл.

Как проверить наличие отрицательного цикла¶

Нужно сделать ещё один, то есть n-й проход по всем рёбрам.

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

bool neg_cycle = false;
for (auto e : edges) {
    if (dist[e.a] == INF) continue;
    if (dist[e.a] + e.w < dist[e.b]) {
        neg_cycle = true;
    }
}

Если нужен именно цикл, а не только факт его существования, его тоже можно восстановить через массив предков.

Полный вариант с проверкой отрицательного цикла¶

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

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

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

    int n, m, s;
    cin >> n >> m >> s;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

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

    bool neg_cycle = false;
    for (auto e : edges) {
        if (dist[e.a] == INF) continue;
        if (dist[e.a] + e.w < dist[e.b]) {
            neg_cycle = true;
        }
    }

    if (neg_cycle) {
        cout << "Есть отрицательный цикл\n";
    } else {
        cout << "Отрицательного цикла нет\n";
    }

    return 0;
}

SPFA algorithm¶

SPFA — это модификация алгоритма Беллмана–Форда. Название расшифровывается как Shortest Path Faster Algorithm.

Идея такая:

в обычном Беллмане–Форде на каждом раунде мы просматриваем все рёбра;
в SPFA мы стараемся смотреть только те вершины, из которых действительно может произойти улучшение.

Для этого используется очередь.

Как работает SPFA¶

Помещаем стартовую вершину в очередь.
Пока очередь не пуста:
берём вершину из начала очереди;
просматриваем все исходящие рёбра;
если расстояние до соседа улучшилось, добавляем соседа в очередь.

Схема:

flowchart TD
    A[Положить стартовую вершину в очередь] --> B{Очередь пуста?}
    B -- Нет --> C[Взять вершину из начала очереди]
    C --> D[Просмотреть все исходящие ребра]
    D --> E{Есть улучшение расстояния?}
    E -- Да --> F[Обновить dist и добавить соседа в очередь]
    E -- Нет --> B
    F --> B
    B -- Да --> G[Алгоритм завершен]

Hold "Ctrl" to enable pan & zoom

Реализация SPFA на C++¶

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

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

    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
    }

    const long long INF = (long long)4e18;
    vector<long long> dist(n + 1, INF);
    vector<bool> inq(n + 1, false);

    queue<int> q;
    dist[s] = 0;
    q.push(s);
    inq[s] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inq[v] = false;

        for (auto [to, w] : adj[v]) {
            if (dist[v] == INF) continue;
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                if (!inq[to]) {
                    q.push(to);
                    inq[to] = true;
                }
            }
        }
    }

    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) cout << "INF\n";
        else cout << dist[v] << "\n";
    }

    return 0;
}

Важное замечание про SPFA¶

SPFA часто работает быстрее обычного Беллмана–Форда на практике, но в худшем случае его асимптотика всё равно остаётся O(n·m). Существуют специальные графы, на которых он работает очень медленно.

Поэтому SPFA — это не магическая замена Беллману–Форду, а скорее практическая эвристика.

Когда какой алгоритм использовать¶

Беллман–Форд¶

Подходит, если:

есть отрицательные рёбра;
нужно проверить отрицательный цикл;
граф не слишком большой.

SPFA¶

Подходит, если:

хочется попробовать ускорить Беллмана–Форда на практике;
граф разреженный;
отрицательные рёбра возможны, но отрицательных циклов нет.

Но всегда нужно помнить про плохой худший случай.

Краткий итог¶

Беллман–Форд делает n-1 проходов по всем рёбрам;
умеет работать с отрицательными весами;
может обнаруживать отрицательные циклы;
SPFA — его очередь-ориентированная модификация;
в теории SPFA не лучше по худшему случаю, но на практике часто быстрее.

13. Кратчайшие пути¶

13.1 Алгоритм Беллмана–Форда¶

Идея алгоритма¶

Почему достаточно n-1 проходов¶

Схема работы¶

Пример¶

Начало¶

После первого прохода¶

Реализация на C++¶

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

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

Как проверить наличие отрицательного цикла¶

Полный вариант с проверкой отрицательного цикла¶

SPFA algorithm¶

Как работает SPFA¶

Реализация SPFA на C++¶

Важное замечание про SPFA¶

Когда какой алгоритм использовать¶

Беллман–Форд¶

SPFA¶

Краткий итог¶

Почему достаточно `n-1` проходов¶