13.2 Алгоритм Дейкстры¶

Алгоритм Дейкстры решает задачу поиска кратчайших путей от одной стартовой вершины до всех остальных в взвешенном графе без отрицательных рёбер.

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

Когда применять алгоритм Дейкстры¶

Алгоритм подходит, если:

• дан граф с весами рёбер;
• нужно найти минимальные расстояния от одной вершины s до всех остальных;
• все веса рёбер неотрицательны.

Если в графе есть хотя бы одно отрицательное ребро, использовать алгоритм Дейкстры нельзя: ответ может оказаться неверным.

Основная идея¶

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

В начале:

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

Дальше алгоритм действует так:

1. выбирает непомеченную вершину с минимальным значением dist;
2. объявляет это расстояние окончательным;
3. пытается улучшить расстояния до её соседей.

Этот шаг улучшения расстояний называется релаксацией.

Если есть ребро v -> to веса w, то мы проверяем:

если dist[v] + w < dist[to],
то dist[to] = dist[v] + w

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

Небольшой пример¶

Рассмотрим граф. Стартовая вершина — 1.

flowchart LR
    n1((1)) -- 4 --> n2((2))
    n1 -- 2 --> n3((3))
    n2 -- 5 --> n4((4))
    n3 -- 1 --> n2
    n3 -- 7 --> n4
    n2 -- 3 --> n5((5))
    n4 -- 1 --> n5

Найдём кратчайшие расстояния от вершины 1.

Шаг 0¶

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

Шаг 1¶

Берём вершину 1, потому что у неё минимальное расстояние 0.

Релаксируем рёбра:

• 1 -> 2 с весом 4, получаем dist[2] = 4
• 1 -> 3 с весом 2, получаем dist[3] = 2

Теперь:

dist = [0, 4, 2, INF, INF]

Шаг 2¶

Среди необработанных минимальна вершина 3, потому что dist[3] = 2.

Релаксируем рёбра из 3:

• 3 -> 2 с весом 1: новый путь до 2 равен 2 + 1 = 3, это лучше, чем 4
• 3 -> 4 с весом 7: получаем dist[4] = 9

Теперь:

dist = [0, 3, 2, 9, INF]

Шаг 3¶

Берём вершину 2, так как dist[2] = 3.

Релаксируем:

• 2 -> 4 с весом 5: путь длины 3 + 5 = 8, улучшаем dist[4]
• 2 -> 5 с весом 3: получаем dist[5] = 6

Теперь:

dist = [0, 3, 2, 8, 6]

Шаг 4¶

Берём вершину 5, потому что dist[5] = 6.

Из неё улучшений нет.

Шаг 5¶

Берём вершину 4, потому что dist[4] = 8.

Ребро 4 -> 5 с весом 1 не улучшает ответ, потому что 8 + 1 = 9, а dist[5] = 6.

Ответ¶

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

Почему расстояние становится окончательным¶

Это ключевая идея алгоритма.

Когда мы выбираем необработанную вершину v с минимальным dist[v], мы утверждаем, что более короткого пути до неё уже не существует.

Почему?

• любой другой путь до v должен проходить через какую-то ещё необработанную вершину;
• у такой вершины расстояние не меньше, чем dist[v], потому что v выбрана как минимальная;
• все веса неотрицательны, значит добавить ещё рёбра и сделать путь короче невозможно.

Поэтому после выбора вершины её расстояние можно считать финальным.

Реализация через приоритетную очередь¶

На практике алгоритм почти всегда пишут через priority_queue.

Идея такая:

• в очереди храним пары (расстояние, вершина);
• каждый раз достаём вершину с минимальным расстоянием;
• пытаемся улучшить соседей.

Так как стандартная priority_queue в C++ — это максимум-куча, удобнее использовать greater<>, чтобы очередь работала как минимум-куча.

Код на C++¶

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

const long long INF = (long long)4e18;

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

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

    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});
        // Если граф неориентированный, добавьте ещё:
        // adj[b].push_back({a, w});
    }

    int s;
    cin >> s;

    vector<long long> dist(n + 1, INF);
    vector<int> parent(n + 1, -1);
    vector<bool> used(n + 1, false);

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

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

    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();

        if (used[v]) continue;
        used[v] = true;

        for (auto [to, w] : adj[v]) {
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                parent[to] = v;
                pq.push({dist[to], to});
            }
        }
    }

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

    return 0;
}

Что означают массивы в коде¶

dist[v]¶

Текущее лучшее найденное расстояние от старта до вершины v.

used[v]¶

Показывает, обработана ли вершина окончательно.

parent[v]¶

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

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

Если нужно получить путь от s до t, после работы алгоритма можно пройти назад по массиву parent.

Код восстановления пути¶

vector<int> get_path(int s, int t, const vector<int>& parent) {
    vector<int> path;
    if (s == t) {
        path.push_back(s);
        return path;
    }
    if (parent[t] == -1) return path;

    int cur = t;
    while (cur != -1) {
        path.push_back(cur);
        if (cur == s) break;
        cur = parent[cur];
    }

    reverse(path.begin(), path.end());
    if (path.front() != s) path.clear();
    return path;
}

Пример использования¶

int t = 5;
vector<int> path = get_path(s, t, parent);

if (path.empty()) {
    cout << "Пути нет\n";
} else {
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

Важная деталь: почему в очереди может быть одна вершина много раз¶

В реализации через priority_queue одна и та же вершина действительно может быть добавлена в очередь несколько раз.

Например:

• сначала нашли путь длины 10;
• потом нашли путь длины 7;
• в очереди окажутся обе записи.

Это нормально. Когда мы достанем устаревшую запись, вершина уже окажется обработанной, и мы просто пропустим её:

if (used[v]) continue;

Это стандартный и очень удобный приём.

Почему алгоритм не работает с отрицательными рёбрами¶

Рассмотрим пример:

flowchart LR
    a((1)) -- 2 --> b((2))
    a -- 7 --> c((3))
    c -- -10 --> d((4))
    b -- 3 --> d

Если стартовать из вершины 1, алгоритм сначала решит, что путь до 2 равен 2, а до 3 — 7.

Затем он может слишком рано зафиксировать вершину 2 и путь через неё к 4 длины 5. Но позже оказалось бы, что путь 1 -> 3 -> 4 имеет длину -3, то есть он лучше.

Проблема в том, что отрицательное ребро может резко улучшить путь позже, после того как какая-то вершина уже считалась окончательно обработанной.

Поэтому:

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

Асимптотика¶

Наивная реализация¶

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

O(n^2 + m)

Такая версия может быть полезна для плотных графов или при маленьких ограничениях.

Реализация с priority_queue¶

Самая популярная версия работает за:

O((n + m) log m)

Часто это также записывают как:

O(m log n)

для разреженных графов.

Именно эта версия обычно нужна в олимпиадных задачах.

Когда какая реализация лучше¶

Если граф разреженный¶

То есть рёбер примерно столько же, сколько вершин, или ненамного больше:

• используем список смежности;
• используем priority_queue.

Это стандартный выбор.

Если граф плотный¶

То есть рёбер очень много, близко к n^2, иногда может подойти и реализация за O(n^2) без очереди.

Но в большинстве соревновательных задач всё же удобнее и привычнее версия с кучей.

Типичные ошибки¶

1. Использовать Дейкстру при отрицательных весах¶

Это самая частая концептуальная ошибка.

2. Хранить расстояния в int, когда суммы могут быть большими¶

Если веса и длины путей большие, используйте long long.

3. Забыть добавить обратное ребро в неориентированном графе¶

Для неориентированного графа надо писать:

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

4. Пытаться восстанавливать путь без массива parent¶

Если нужен маршрут, его надо сохранять во время релаксаций.

5. Неправильно выбрать INF¶

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

Упрощённая версия Дейкстры без восстановления пути¶

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

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

const long long INF = (long long)4e18;

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

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

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

    vector<long long> d(n + 1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q;

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

    while (!q.empty()) {
        auto [cur, v] = q.top();
        q.pop();

        if (cur != d[v]) continue;

        for (auto [to, w] : g[v]) {
            if (d[v] + w < d[to]) {
                d[to] = d[v] + w;
                q.push({d[to], to});
            }
        }
    }

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

Здесь используется другой популярный приём:

if (cur != d[v]) continue;

Он отбрасывает устаревшие записи в очереди и позволяет обойтись без массива used.

Сравнение с алгоритмом Беллмана–Форда¶

Алгоритм Дейкстры¶

• быстрее;
• подходит для больших графов;
• требует неотрицательных весов.

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

• медленнее;
• работает и с отрицательными рёбрами;
• умеет обнаруживать отрицательные циклы.

Обычно выбор такой:

• нет отрицательных рёбер → Дейкстра;
• есть отрицательные рёбра → Беллман–Форд или его вариации.

Где встречается алгоритм Дейкстры¶

Частые формулировки задач:

• минимальная стоимость пути;
• кратчайшее время до всех городов;
• самый дешёвый маршрут в транспортной сети;
• минимальная энергия/топливо/плата за перемещение;
• путь на клетчатом поле, если клетки или переходы имеют цены.

Если поле можно рассматривать как граф, где клетки — вершины, а переходы — рёбра с весами, Дейкстра также отлично работает.

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

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

Его главные идеи:

• храним текущие расстояния;
• каждый раз выбираем вершину с минимальным расстоянием;
• релаксируем её рёбра;
• используем приоритетную очередь для ускорения.

Нужно запомнить три вещи:

1. алгоритм работает только без отрицательных рёбер;
2. стандартная реализация — список смежности + priority_queue;
3. для восстановления пути нужен массив parent.

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