Алгоритм Дейкстры простыми словами

Алгоритм Дейкстры находит кратчайшие пути от одной точки до всех остальных, когда у дорог разная длина. Ниже — полная теория из курса «Кружок 102» с разбором, как и почему он работает.

Зачем это нужно

BFS находит кратчайшие пути в графе, где все рёбра «стоят» одинаково — по сути, считает количество рёбер. Но в жизни рёбра почти всегда разные: дорога может быть длинной или короткой, перелёт — дешёвым или дорогим, канал — быстрым или медленным. Как только у рёбер появляются веса, обычный BFS ломается: он может «выйти» из вершины раньше, чем найдёт до неё по-настоящему кратчайший путь, потому что идёт строго по слоям, не разбирая, что один путь в два шага может быть длиннее, чем другой в пять шагов.

Алгоритм Дейкстры — это ответ на вопрос «как искать кратчайшие пути во взвешенном графе, если веса рёбер неотрицательны». Он находит расстояния от одной стартовой вершины до всех остальных за один проход, без переборов и пересчётов «с нуля». Это один из самых используемых алгоритмов в олимпиадном программировании и в реальной жизни — так работает, например, часть логики в картах и роутинге пакетов в сети.

Идея на пальцах

Представь, что ты заливаешь граф водой из стартовой вершины s. Вода течёт по рёбрам, и время, за которое она добирается до вершины v по конкретному ребру, равно весу этого ребра. Вода из s расходится во все стороны одновременно, и вершина «намокает» в момент, когда до неё доходит *первая* волна воды — а это и есть кратчайшее расстояние.

Ключевое наблюдение: вершины «намокают» строго в порядке возрастания расстояния от старта. Это интуитивно понятно — если до вершины A вода дошла раньше, чем до вершины B, то расстояние до A меньше. Дейкстра — это ровно симуляция такого процесса, только без непрерывного времени: на каждом шаге мы берём ещё не «намокшую» вершину с наименьшей текущей оценкой расстояния и объявляем её окончательно намокшей.

Алгоритм

Заводим массив d[] — текущие оценки расстояний (изначально d[s] = 0, остальные = ∞), и массив пометок u[] — обработана вершина или нет.

Дальше n раз повторяем:

1. Среди ещё не помеченных вершин находим ту, у которой d[v] минимально.
2. Помечаем её как обработанную — это финальный ответ для неё.
3. Делаем релаксацию всех рёбер, исходящих из v: для каждого ребра (v, to, w) проверяем, не короче ли путь через v: если d[v] + w < d[to], то обновляем d[to] = d[v] + w.

Релаксация — общее для всех алгоритмов кратчайших путей действие: мы пытаемся улучшить оценку расстояния до to, пройдя через уже известную оценку до v плюс вес ребра. Если получилось лучше — обновляем и (если нужно восстанавливать путь) запоминаем предка: p[to] = v.

Когда очередная выбранная вершина имеет d[v] = ∞, дальше можно останавливаться: оставшиеся вершины недостижимы.

Почему это вообще работает

Это не очевидно: алгоритм на каждом шаге принимает решение «жадно» (берёт минимум) и никогда не пересматривает его для уже помеченных вершин. Нужно доказать, что это не приводит к ошибке.

Утверждение. В момент, когда вершина v помечается, d[v] уже равно настоящему кратчайшему расстоянию до неё, и больше никогда не изменится.

Доказательство по индукции по порядку пометки вершин.

*База.* Первой всегда помечается сама s с d[s]=0 — это, очевидно, кратчайшее расстояние.

*Переход.* Пусть утверждение верно для всех уже помеченных вершин, и сейчас алгоритм выбирает следующую вершину v с минимальным d[v] среди непомеченных. Рассмотрим настоящий кратчайший путь P из s в v длины l(v). Пройдём по нему от s: какое-то время он идёт по уже помеченным вершинам, а затем впервые попадает в непомеченную. Назовём эту первую непомеченную вершину на пути p.

Раз участок пути до p состоит из помеченных вершин, для которых (по предположению индукции) d уже верны, то ребро, ведущее в p, было релаксировано из правильного значения — значит d[p] уже равно истинному расстоянию l(p) до p (может, было улучшено ещё раньше, но не больше истинного, и не меньше — расстояния не бывают заниженными, потому что d всегда получается как сумма весов реального пути).

Дальше используем неотрицательность весов: оставшийся кусок пути от p до v не может уменьшить длину, поэтому l(p) ≤ l(v), то есть d[p] = l(p) ≤ l(v) ≤ d[v] (последнее неравенство — потому что d[v] по построению всегда ≥ истинного расстояния, ведь это длина какого-то пути, а не короче).

Но алгоритм выбрал на этом шаге именно v, а не p, как вершину с минимальным d среди непомеченных. Значит d[v] ≤ d[p]. Вместе с d[p] ≤ d[v] это даёт d[v] = d[p] = l(p) ≤ l(v) ≤ d[v], откуда всё сжимается в равенства: d[v] = l(v). Это и есть то, что требовалось.

Вот здесь и прячется единственное место, где алгоритму нужна неотрицательность весов: если бы вес мог быть отрицательным, оставшийся кусок пути от p до v мог бы «съедать» длину, и неравенство l(p) ≤ l(v) перестало бы быть верным — тогда более длинный на вид путь через ещё не обработанную вершину мог бы в итоге оказаться короче. Поэтому с отрицательными весами Дейкстра ломается, и для таких графов используют Беллмана-Форда — его мы разберём в следующей теме.

Сложность и реализации

Узкое место алгоритма — поиск вершины с минимальным d среди непомеченных на каждом шаге. От того, как это делать, зависит итоговая сложность.

Наивная реализация — O(n²+ m). На каждой из n итераций линейно ищем минимум по массиву d за O(n), суммарно O(n²), плюс каждое ребро релаксируется не более одного раза — суммарно O(m). Хороша для плотных графов, где m ≈ n²: тогда куча ничего не выигрывает, а простой цикл проще писать и у него нет накладных расходов на структуру данных.

const int INF = 1e9; // «бесконечность»: заведомо больше любого реального расстояния

vector<int> dijkstra(int s, vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<int> d(n, INF);
    vector<bool> used(n, false);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++)
            if (!used[j] && (v == -1 || d[j] < d[v])) v = j;
        if (d[v] == INF) break;
        used[v] = true;
        for (auto [to, w] : adj[v])
            if (d[v] + w < d[to]) d[to] = d[v] + w;
    }
    return d;
}

С приоритетной очередью — O(m log n). Вместо линейного поиска минимума кладём пары (d[v], v) в кучу и достаём минимум за O(log n). Проблема в том, что «уменьшить ключ» у уже лежащего в куче элемента напрямую нельзя — стандартный priority_queue этого не умеет. Поэтому поступают проще: при каждой успешной релаксации просто кладут в кучу новую пару, не трогая старую. В куче может оказаться несколько устаревших записей для одной вершины, но это не страшно — при извлечении просто проверяем, не устарела ли запись, и если да, пропускаем её:

vector<int> dijkstra(int s, vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<int> d(n, INF);
    d[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [cur_d, v] = pq.top(); pq.pop();
        if (cur_d > d[v]) continue; // устаревшая запись
        for (auto [to, w] : adj[v]) {
            if (d[v] + w < d[to]) {
                d[to] = d[v] + w;
                pq.push({d[to], to});
            }
        }
    }
    return d;
}

Каждое ребро может добавить в кучу максимум одну запись, значит суммарно операций с кучей O(m), каждая стоит O(log m) = O(log n) (так как m ≤ n²), итого O(m log n). Для разреженных графов (m ≈ n) это ощутимо быстрее наивных O(n²).

Теоретически ещё лучше — фибоначчиева куча даёт O(n log n + m) засчёт настоящего decrease-key за амортизированный O(1), но на практике её почти никогда не пишут: константа большая, а выигрыш обычно съедается сложностью реализации.

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

Если нужен не только ответ «сколько», а ещё и сам путь, заводят массив предков p[]: при каждой успешной релаксации ребра (v → to) записываем p[to] = v. После работы алгоритма путь до вершины t восстанавливается разворотом цепочки предков: идём t, p[t], p[p[t]], … пока не дойдём до s, а затем разворачиваем полученный список.

Дейкстра по сетке

Сетка (клетчатое поле) — это неявный взвешенный граф: каждая клетка (i, j) — вершина, а переход в соседнюю клетку — ребро. Вес ребра задаётся условием: например, стоимость входа в клетку (клетки-«болота» дороже, клетки-«стены» непроходимы). Явно строить список смежности не нужно — соседей клетки генерируем на лету по сдвигам вверх/вниз/влево/вправо. Запускаем ту же Дейкстру, только в приоритетной очереди лежат не номера вершин, а состояния-клетки (i, j):

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
pq.push({0, si, sj}); // {расстояние, i, j}

Дальше всё как обычно: достаём клетку с минимальным расстоянием, перебираем 4 соседа (ni, nj) в пределах поля и релаксируем d[ni][nj] по весу входа в соседнюю клетку. Мини-пример: на поле 3×3 с временем входа в каждую клетку из матрицы можно найти минимальное суммарное время пути из угла (0,0) в угол (2,2) — это в точности Дейкстра, где вес ребра равен стоимости клетки-приёмника.

Частные случаи и практические моменты

Если веса рёбер — это времена, стоимости или что угодно неотрицательное, но нужен путь с минимальным *количеством рёбер* среди всех кратчайших по весу — на это стандартная Дейкстра ответа не даёт, придётся сравнивать пары (расстояние, число рёбер) как составной ключ.

Если требуется не «расстояния от одной вершины до всех», а «от всех до всех» — на плотных графах есть смысл сразу писать Флойда-Уоршелла за O(n³), а не запускать Дейкстру n раз.

Часто веса рёбер по условию задачи равны 0 или 1 (например, «переключить лампочку — 1 секунда, пройти без действия — 0 секунд») — в таком случае вместо кучи с O(m log n) можно использовать 0-1 BFS с деком за O(n + m), это частный, более быстрый случай той же идеи «обрабатывать вершины в порядке возрастания расстояния».

Наконец, стоит помнить, что Дейкстра ищет кратчайшие пути *от одной вершины ко всем* (single-source shortest paths). Если по смыслу задачи веса могут быть отрицательными — например, есть операции, которые не увеличивают, а уменьшают какую-то величину — доказательство корректности выше перестаёт работать буквально в том месте, где используется неотрицательность весов, и нужен алгоритм Беллмана-Форда, который допускает отрицательные рёбра (но не отрицательные циклы) ценой худшей сложности O(nm).