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

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

Дейкстра чинит это ровно одним изменением: вместо обычной очереди берём очередь с приоритетом и всегда разворачиваем ближайшую ещё не развёрнутую вершину.

Инвариант

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

Утверждение: если среди неразвёрнутых взять вершину с наименьшим $d[v]$, её значение уже окончательное.

Почему. Пусть есть путь до $v$ короче, чем $d[v]$. Он выходит из развёрнутой области и где-то первый раз попадает в неразвёрнутую — в вершину $u$. Тогда $d[u]$ не больше длины начала этого пути, а значит и не больше всей его длины (остаток неотрицателен). Но мы выбрали $v$ как минимум, значит $d[v] \le d[u]$, и путь не короче. Противоречие.

Слова «остаток неотрицателен» — здесь единственное место, где используются условия на веса. Отрицательное ребро ломает доказательство целиком.

Реализация за $O(n^2)$

На каждом шаге ищем минимум перебором. Годится, когда граф плотный ($m$ близко к $n^2$) или когда рёбра не хранятся вовсе, а вычисляются по формуле.

const long long INF = 4e18;

vector<long long> dijkstra(int s) {
    vector<long long> d(n, INF);
    vector<char> used(n, 0);
    d[s] = 0;
    for (int it = 0; it < n; it++) {
        int v = -1;
        for (int u = 0; u < n; u++)
            if (!used[u] && d[u] < INF && (v == -1 || d[u] < d[v])) v = u;
        if (v == -1) break;              // остальные недостижимы
        used[v] = 1;
        for (auto [to, c] : g[v])
            if (d[v] + c < d[to]) d[to] = d[v] + c;
    }
    return d;
}

При $n = 3000$ это порядка девяти миллионов операций поиска минимума — заходит спокойно, а логарифмов нет вовсе.

Реализация за $O(m \log n)$

Разреженный граф просит очередь с приоритетом. В priority_queue нельзя удалить произвольный элемент, поэтому улучшенное расстояние просто кладут ещё раз, а старые записи отбрасывают при извлечении.

vector<long long> dijkstra(int s) {
    vector<long long> d(n, INF);
    d[s] = 0;
    priority_queue<pair<long long, int>,
                   vector<pair<long long, int>>,
                   greater<>> q;
    q.push({0, s});
    while (!q.empty()) {
        auto [dv, v] = q.top(); q.pop();
        if (dv > d[v]) continue;         // устаревшая запись — вот эта строка
        for (auto [to, c] : g[v])
            if (d[v] + c < d[to]) { d[to] = d[v] + c; q.push({d[to], to}); }
    }
    return d;
}

greater<> нужен потому, что куча в C++ по умолчанию отдаёт максимум, а нам нужен минимум. Подробности — в статье про кучу.

Строка, без которой всё разваливается

Если убрать if (dv > d[v]) continue;, ответ останется верным — но вершину начнут разворачивать по многу раз, и каждый раз заново просматривать все её рёбра.

Граф, на котором это видно: старт соединён рёбрами веса 1 со всеми остальными вершинами, а «жертва» соединена с теми же вершинами рёбрами убывающего веса. Очередь достаёт соседей по очереди, каждый улучшает расстояние до жертвы, жертва попадает в кучу $n-2$ раза.

$n$	рёбер	просмотров рёбер с проверкой	без проверки
100	392	392	9 898
300	1 192	1 192	89 698
1 000	3 992	3 992	998 998
3 000	11 992	11 992	8 996 998

Измерено. С проверкой работа равна ровно $m$; без неё растёт как $n^2$.

Можно обойтись и без сравнения расстояний — завести массив used и делать continue, если вершина уже развёрнута. Разницы нет, но версия с dv > d[v] короче и не требует лишней памяти.

Вариант на set

set умеет удалять произвольный элемент, поэтому устаревших записей не возникает вовсе:

set<pair<long long, int>> q;
q.insert({0, s});
while (!q.empty()) {
    auto [dv, v] = *q.begin(); q.erase(q.begin());
    for (auto [to, c] : g[v])
        if (dv + c < d[to]) {
            q.erase({d[to], to});        // удаляем старое значение
            d[to] = dv + c;
            q.insert({d[to], to});
        }
}

Та же асимптотика, но константа заметно хуже: set — красно-чёрное дерево с указателями, куча — массив. На плотных графах разница между set и priority_queue бывает в разы, и она решает.

Проверено: на четырёх тысячах случайных графов до восьми вершин все три реализации совпали с алгоритмом Беллмана — Форда.

Отрицательные веса

Дейкстру на них запускать нельзя. Минимальный пример: рёбра $s \to a$ веса 3, $s \to b$ веса 5, $b \to a$ веса $-4$, $a \to c$ веса 0.

Верный ответ $d[c] = 1$: идём через $b$. Дейкстра разворачивает $a$ со значением 3 раньше, чем находит короткий путь, — и возвращает 3.

Измерено на 145 637 случайных графах с отрицательными рёбрами (без отрицательных циклов): версия с used ошиблась на 4% из них. Ленивая версия на priority_queue ответ давала верный всегда — она просто разворачивает вершину заново, когда расстояние улучшилось, — но теряет свою гарантию: одну вершину она разворачивала до пяти раз на графе из восьми вершин. Так делать нельзя: это уже не Дейкстра, а Беллман — Форд с кучей, и оценки $O(m \log n)$ у него нет.

С отрицательными рёбрами берут Флойда или Беллмана — Форда.

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

Заводим массив предков и обновляем его там же, где расстояние:

if (d[v] + c < d[to]) { d[to] = d[v] + c; par[to] = v; q.push({d[to], to}); }

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

Где Дейкстра появляется неожиданно

Веса на вершинах, а не на рёбрах. Задача про заправки: проехать по дороге можно, только заправившись в городе, откуда выезжаешь. Значит, ребро $v \to u$ стоит столько, сколько стоит бензин в $v$. Неориентированное ребро превращается в два ориентированных с разными весами, и дальше — обычная Дейкстра.

Граф не задан явно. Точки на плоскости, стоимость перехода — квадрат расстояния. Матрица смежности на $10^4$ точек не влезет в память, а версия за $O(n^2)$ вообще не хранит рёбер: она считает вес по формуле в момент перебора соседей. Подробнее — неявный граф.

Состояние сложнее вершины. Вершина плюс дополнительная информация — тоже вершина. Про это отдельная статья.