eduplan-cpp-eltex/diag/tasks/12_dijkstra/task.md

Задача 12 — Дейкстра на priority_queue (C++)

long long shortest_path(int n,
                        const std::vector<std::tuple<int,int,int>>& edges,  // (u, v, w)
                        int src, int dst);

Требования:

• рёбра ориентированные, вес w >= 0, self-loop допустим; вершины 0..n-1;
• вернуть длину кратчайшего пути src -> dst (long long, веса суммируются до 10^9);
• недостижимость → -1; src == dst → 0;
• вес рёбер 0 допустим (условие применимости Дейкстры — неотрицательные веса);
• 100 000 вершин и 200 000 рёбер: быстрее 2 секунд. Значит нужна std::priority_queue (O((V+E) log V)), а не O(V²) перебор минимума.

Проверка: python3 grade.py 12. Критерий: все ok, сборка без предупреждений.

Факты для карточек

• base | Что возвращает функция при src == dst? — 0
• base | Что возвращает функция при недостижимости dst? — -1
• base | В каком типе суммируются веса и почему не int? — long long; веса суммируются до 10^9, int может переполниться на длинном пути

Почему дальше: чтобы уложиться в 2 секунды на 100 000 вершин и 200 000 рёбер, важно понять, почему наивный перебор минимума не подходит и что именно даёт куча.

Механизм: куча против наивного перебора

Наивная Дейкстра. На каждом из V шагов алгоритм сканирует массив dist[] целиком, чтобы найти непосещённую вершину с минимальным расстоянием — это O(V) на шаг. Суммарно V шагов по O(V) — O(V²), плюс O(E) на релаксацию рёбер (эта часть не доминирует). Подходит, если граф плотный (E ~ V²), но не в этой задаче.

Дейкстра с priority_queue. Вместо линейного скана используется min-куча по текущему известному расстоянию. При релаксации ребра (u, v, w), если найден более короткий путь до v, в кучу добавляется новая запись (dist, v) — push стоит O(log размер_кучи). Так как для одной вершины может накопиться несколько записей (по одной на каждое улучшение расстояния), размер кучи ограничен числом релаксаций, то есть O(V + E), и log от этой величины по порядку — тот же O(log V) (log(V²) = 2 log V, то есть смена основания не меняет асимптотику). Суммарно: O((V + E) log V).

Числа задачи. V = 100 000, E = 200 000. Наивный O(V²) = 100 000² = 10^10 операций — в 2 секунды не укладывается ни при каких обстоятельствах. Куча: (V+E)·log₂V ≈ 300 000 · 16,6 ≈ 5·10^6 операций — на 3–4 порядка меньше, укладывается с большим запасом.

«Ленивое» удаление устаревших записей. std::priority_queue не умеет decrease-key за O(log n) (не тот интерфейс), поэтому вместо обновления существующей записи в куче для вершины v просто добавляется новая пара (dist, v) при каждом улучшении. В куче одновременно может лежать несколько устаревших записей для одной вершины. При извлечении самой записи с минимальным dist проверяется, актуальна ли она:

auto [d, v] = pq.top(); pq.pop();
if (d != dist[v]) continue;   // запись устарела — лучшая уже обработана раньше

Это дешевле, чем поддерживать структуру с настоящим decrease-key (например, indexed heap), и корректность не страдает — устаревшая запись всегда хуже уже найденного dist[v] и просто пропускается.

Факты для карточек

• base | Сложность наивной Дейкстры (перебор минимума по массиву)? — O(V²)
• base | Сложность Дейкстры с бинарной кучей? — O((V+E) log V)
• core | При V=100 000, E=200 000, почему наивный O(V²) не укладывается в 2 секунды? — 100 000² = 10^10 операций против ≈5·10^6 у варианта с кучей — разница на 3–4 порядка
• core | Что означает «ленивое удаление» устаревших записей в очереди? — вместо decrease-key при каждом улучшении расстояния в кучу пушится новая пара (dist, v); при извлечении запись с d != dist[v] пропускается как устаревшая
• deep | Почему std::priority_queue не используют с decrease-key напрямую? — у контейнера-адаптера нет интерфейса для обновления произвольного элемента за O(log n); дешевле каждый раз пушить новую запись и лениво отбрасывать устаревшие при pop

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

Механизм: почему нужны только неотрицательные веса

Дейкстра — жадный алгоритм: когда вершина v извлекается из очереди с минимальным на данный момент расстоянием, алгоритм считает dist[v] окончательным и больше не пересматривает эту вершину. Это верно только если все ещё не обработанные пути до v не могут оказаться короче — а это гарантировано лишь при неотрицательных весах: любой другой путь до v проходит через вершины с расстоянием ≥ dist[v] и добавляет ребро ≥ 0, то есть не может дать сумму меньше dist[v].

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

Для графов с отрицательными весами (без отрицательных циклов) используется Беллман-Форд: V-1 раз релаксируются все E рёбер, O(V·E). Дополнительно на V-м проходе можно проверить, продолжает ли что-то релаксироваться — если да, в графе отрицательный цикл, кратчайший путь не определён (можно уменьшать бесконечно).

Self-loop с весом w ≥ 0 никогда не уменьшает кратчайший путь (добавление неотрицательного веса к текущему расстоянию не улучшает его), поэтому не требует отдельной обработки — алгоритм просто никогда не выберет такое ребро для релаксации выгодно.

Факты для карточек

• core | Почему Дейкстра ломается на отрицательных рёбрах? — алгоритм считает расстояние до извлечённой из очереди вершины окончательным; отрицательное ребро может позже уменьшить это расстояние, но вершина уже не пересматривается
• base | Какой алгоритм нужен при отрицательных весах без отрицательных циклов? — Беллман-Форд, O(V·E)
• core | Как Беллман-Форд обнаруживает отрицательный цикл? — если рёбра продолжают релаксироваться на V-м проходе (после V-1 гарантированно достаточных проходов), в графе есть отрицательный цикл
• base | Почему self-loop с w≥0 не требует отдельной обработки? — добавление неотрицательного веса к текущему расстоянию никогда не уменьшает его, значит такое ребро никогда не выигрывает релаксацию

Ловушки

• Использовать int вместо long long для накопленной суммы весов → при весах рёбер до 10^9 и длинном пути сумма переполняет int → тихо неверный (отрицательный или «случайный») результат без явного падения.
• Забыть проверку if (d != dist[v]) continue при извлечении из очереди → обрабатываются устаревшие записи повторно → не влияет на корректность, но раздувает число операций и на 200 000 рёбер может вывести время за лимит 2 секунды.
• Запустить алгоритм на графе с отрицательным ребром без проверки условия применимости → результат тихо неверный (нет явной ошибки времени выполнения) — Дейкстра не обнаруживает нарушение своего предположения сама.
• Перепутать направление рёбер (граф ориентированный) и релаксировать в обе стороны → находится путь, которого нет в графе условия задачи, shortest_path возвращает заниженное значение.

Проверь себя

1. Почему при V=100 000 и E=200 000 наивный O(V²) не проходит по времени, а вариант с кучей — проходит?

`O(V²) = 100 000² = 10^10` операций — на 3–4 порядка больше, чем позволяют 2 секунды. Вариант с кучей — `O((V+E) log V) ≈ 300 000 · log₂(100 000) ≈ 300 000 · 16,6 ≈ 5·10^6` операций, укладывается с большим запасом.

2. Что произойдёт с результатом Дейкстры, если в графе есть ребро веса -5, а остальные рёбра положительные?

Результат может быть неверным без явной ошибки: если вершина на дешёвом с виду пути уже извлечена из очереди и «финализирована», а позже к ней ведёт более короткий путь через ребро -5, алгоритм это улучшение не увидит, так как вершина повторно не пересматривается.

3. Почему в очереди могут одновременно лежать несколько записей для одной и той же вершины, и почему это не ошибка?

Каждое найденное улучшение расстояния до вершины добавляет новую запись `(dist, v)` в кучу вместо обновления старой (`decrease-key` не поддерживается `std::priority_queue`). Это не ошибка, потому что при извлечении устаревшая запись (`d != dist[v]`) просто пропускается — корректность сохраняется, платится только лишней памятью в очереди и лишним `pop`.

4. Почему self-loop с весом w≥0 никогда не меняет кратчайший путь?

Self-loop добавляет вершине путь до самой себя длиной `w ≥ 0`. Поскольку путь длины 0 (не двигаться) уже не хуже, прибавление неотрицательного веса к текущему `dist[v]` не может дать меньшее значение — релаксация через такое ребро никогда не проходит условие «короче».