Dijkstra | kz-maxx

Что такое алгоритм Дейкстры?

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

Он работает, когда у ребер есть веса, но все веса должны быть неотрицательными.

Если в графе есть отрицательные ребра, обычная Дейкстра не подходит. Тогда нужен алгоритм Беллмана-Форда.

Где используется?

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

Главная идея

Мы храним массив dist.

dist[v]

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

В начале:

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

Потом мы постепенно улучшаем расстояния.

если dist[v] + вес ребра меньше dist[to]
значит нашли путь лучше
обновляем dist[to]

if (dist[v] + w < dist[to]) {
    dist[to] = dist[v] + w;
}

Что такое relaxation?

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

Допустим:

dist[v] = 5
ребро v → to имеет вес 3
тогда путь до to через v равен 5 + 3 = 8

Если раньше было:

dist[to] = 15

Тогда новый путь лучше:

8 < 15
dist[to] = 8

Почему нужен priority_queue?

Каждый раз нам нужно брать вершину с минимальным текущим расстоянием.

Для этого удобно использовать:

priority_queue

Но в C++ обычный priority_queue — это max-heap. Нам нужен min-heap, поэтому пишем так:

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

В queue кладем пару:

{расстояние, вершина}

Пример графа

Пусть есть граф:

1 --5-- 2
1 --2-- 3
3 --1-- 2
2 --3-- 4
3 --7-- 4

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

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

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

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

1 → 3 → 2
2 + 1 = 3

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

1 → 3 → 2 → 4
2 + 1 + 3 = 6

Структура графа

Так как у ребра есть вес, в списке смежности храним пару:

vector<pair<int, int>> g[N];

Здесь:

first — вершина, куда идет ребро
second — вес ребра

Например, если есть ребро:

1 --5-- 2

Тогда добавляем:

g[1].push_back({2, 5});
g[2].push_back({1, 5});

Базовая функция Дейкстры

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}

Зачем нужен if (d != dist[v])?

В priority_queue может лежать старая информация.

Например, сначала мы нашли путь до вершины 2 длиной 10. Потом нашли путь лучше — длиной 3.

В queue может лежать:
{10, 2}
{3, 2}

Когда достаем старую пару {10, 2}, она уже не нужна. Поэтому мы ее пропускаем.

if (d != dist[v]) {
    continue;
}

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

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

Input

Output

0 3 2 6

Формат:

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;

int n, m, s;
vector<pair<int, int>> g[N];
long long dist[N];

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}

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;

        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dijkstra(s);

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

    return 0;
}

Восстановление кратчайшего пути

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

int p[N];

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

p[to] = v;

То есть:

в вершину to мы пришли из вершины v

Как восстановить путь?

Идем от конечной вершины назад по parent.

vector<int> path;

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

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

Например:

путь 1 → 3 → 2 → 4
p[4] = 2
p[2] = 3
p[3] = 1
p[1] = -1

Задача 2: найти кратчайший путь

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

Input

Output

1 3 2 4

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

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

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

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

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                p[to] = v;
                q.push({dist[to], to});
            }
        }
    }
}

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;

        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dijkstra(s);

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

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

Если граф ориентированный, то ребро идет только в одну сторону.

Для ребра:

a → b с весом w

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

g[a].push_back({b, w});

А вот это уже не нужно:

g[b].push_back({a, w});

Dijkstra vs BFS

Алгоритм	Граф	Что ищет
BFS	невзвешенный	кратчайший путь по количеству ребер
Dijkstra	взвешенный, веса неотрицательные	кратчайший путь по сумме весов

Если все веса равны 1, можно использовать BFS. Если веса разные, нужен алгоритм Дейкстры.

Когда нельзя использовать Дейкстру?

Нельзя использовать обычную Дейкстру, если есть отрицательные веса.

1 → 2 вес 5
1 → 3 вес 2
3 → 2 вес -10

Здесь отрицательное ребро может сломать логику алгоритма.

Для отрицательных ребер используй Bellman-Ford. Для всех пар вершин можно использовать Floyd-Warshall.

Асимптотика

Реализация	Время	Память
priority_queue	O((n + m) log n)	O(n + m)
обычный массив	O(n² + m)	O(n + m)

В олимпиадных задачах чаще всего используют реализацию через priority_queue.

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

const long long INF = 4e18;

vector<pair<int, int>> g[N];
long long dist[N];

void dijkstra(int s) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        auto cur = q.top();
        q.pop();

        long long d = cur.first;
        int v = cur.second;

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}