Дерево кратчайших путей

Массив предков, который заводят для восстановления пути, — это не служебная структура, а полноценный объект. Он задаёт дерево.

Определение

Запустим Дейкстру из вершины $s$ и запомним, откуда пришло финальное значение:

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

У каждой достижимой вершины ровно один предок, у $s$ — ни одного. Получается дерево с корнем в $s$ — дерево кратчайших путей. Путь по дереву от корня до вершины и есть кратчайший путь до неё.

Тот же объект для невзвешенного графа даёт обход в ширину; там он называется деревом обхода и разбирается отдельно.

Главное свойство

Выбросим из графа все рёбра, кроме $n-1$ ребра дерева. Ни одно кратчайшее расстояние от $s$ не изменится.

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

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

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

Задача: 300 вершин, до $10^5$ рёбер с весами. Разрешено удвоить вес одного любого ребра. Сделать кратчайшее расстояние из 1 в $n$ как можно больше.

В лоб: перебрать ребро, удвоить, запустить Дейкстру. Это $O(m \cdot n^2)$ — при $m = 10^5$ и $n = 300$ порядка $10^{10}$ операций, безнадёжно.

С деревом: кандидатов не $m$, а $n - 1$. Все остальные рёбра на ответ не влияют. Получается $O(n \cdot n^2) = O(n^3)$ — при $n = 300$ это $2.7 \cdot 10^7$, спокойно.

long long best = base;                    // расстояние без изменений
for (int v = 0; v < n; v++) {
    if (par_edge[v] < 0) continue;
    best = max(best, dijkstra_with_doubled(par_edge[v])[n - 1]);
}

Обратите внимание: Дейкстру внутри надо брать за $O(n^2)$, а не за $O(m \log n)$. При $m = 10^5$ версия с кучей даёт лишний логарифм там, где он не нужен: $n$ мало, $m$ велико.

Проверено: на 15 935 случайных графах перебор только по рёбрам дерева дал тот же максимум, что перебор по всем рёбрам.

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

Обход из множества источников

Второй приём той же природы. Нужно расстояние от ближайшей вершины из заданного множества $S$ — не от конкретной, а от любой.

Запускать обход из каждой вершины $S$ по очереди — $|S|$ запусков. Не нужно: кладём в очередь сразу все вершины $S$ с расстоянием ноль.

vector<long long> d(n, INF);
priority_queue<pair<long long, int>,
               vector<pair<long long, int>>,
               greater<>> q;
for (int s : sources) { d[s] = 0; q.push({0, s}); }
// дальше всё как обычно

Корректность видна через фиктивную вершину: добавим вершину $S^*$ и рёбра веса 0 из неё во все источники. Расстояние от $S^*$ до $v$ и есть минимум по источникам, а начальное заполнение очереди — ровно первый шаг такой Дейкстры.

Проверено: на трёх тысячах случайных графов многоисточниковый запуск совпал с запуском из фиктивной вершины.

Стоит это один обход, а не $|S|$. Типичные постановки: «расстояние до ближайшего пожарного гидранта», «до ближайшей заправки», «до ближайшей клетки с водой».

Что не переносится

Дерево кратчайших путей — не минимальное остовное дерево. Это разные объекты, и суммарный вес рёбер у них разный.

Простой пример: треугольник с рёбрами $s{-}a = 2$, $s{-}b = 2$, $a{-}b = 1$. Дерево кратчайших путей от $s$ — это два ребра по 2, суммарный вес 4. Минимальное остовное — рёбра 1 и 2, суммарный вес 3. Оно короче, но расстояние от $s$ до $b$ по нему равно 3, а не 2.