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

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

```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` проверяется, актуальна ли она:

```c++
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` возвращает заниженное
  значение.

## Проверь себя

<details>
<summary>1. Почему при V=100 000 и E=200 000 наивный O(V²) не проходит по времени, а вариант
с кучей — проходит?</summary>
`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`
операций, укладывается с большим запасом.
</details>

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

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

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