🧠 ЕГЭ‑2027, задание 23: три способа найти кратчайший путь — какой выбрать?

В демоверсии ЕГЭ‑2027 задание 23 — это поиск кратчайшего пути в ациклическом ориентированном графе по данным из текстового файла. У этой задачи есть как минимум три рабочих подхода — и у каждого свои плюсы и подводные камни. Разберём их не просто «как код», а с прицелом на понимание и гибкость — то, что важно на экзамене.

🔹 Дейкстра (классика)
В чём суть: на каждом шаге выбираем ещё не обработанную вершину с минимальным расстоянием и обновляем соседей.
Плюсы:
✅каноничный алгоритм: если ученик пойдёт на профильные IT‑направления, Дейкстра ему точно пригодится;
✅понятная логика «жадного выбора» — удобно объяснять через аналогии (например, «ищем ближайшую остановку, чтобы оттуда ехать дальше»);
✅легко адаптировать под обязательную вершину: запускаем дважды (старт → обязательная → финиш) и складываем результаты.
Минусы:
❌в «наивной» реализации (линейный поиск минимума) код получается многословным;

🔹 Перебор (упрощённый Форд–Беллман)
В чём суть:
∣V∣−1 раз проходим по всем рёбрам и пытаемся «улучшить» расстояния (релаксация).
Плюсы:
✅максимально простой код: вся логика — в одном условии if w[c] + g[c][d] < w[d];
✅не нужны сложные структуры данных — можно быстро написать на экзамене;
✅хорошо иллюстрирует идею «повторяем, пока можем улучшать».
Минусы:
❌неочевидно, почему достаточно∣V∣−1 итераций — тут нужен отдельный разговор про ацикличность и длину самого длинного пути;
❌менее «универсален» для других типов задач (например, для подсчёта путей).

🔹 Рекурсия + lru_cache
В чём суть: «минимальный путь из A в B — это минимум по всем соседям A из (вес ребра + путь от соседа до B)». Мемоизация хранит уже посчитанные значения.
Плюсы:
✅очень лаконичный код — основная логика умещается в 5–6 строк;
✅идеально ложится на ациклические графы из ЕГЭ‑23;
✅максимальная гибкость: если завтра встретится задача на количество путей (как в задании 13), достаточно заменить min на sum и убрать веса — и это уже другое решение.
Минусы:
❌рекурсия может пугать новичков: важно отдельно проговорить, что без циклов в графе она безопасна;
❌нужно аккуратно следить за глубиной рекурсии и тем, что именно кэшируется.

💡 Что рекомендовать ученикам?
Для экзамена (скорость и надёжность): перебор (Форд–Беллман) или рекурсия с мемоизацией. Оба дают стабильный результат и легко проверяются.
Для олимпиад и дальнейшего пути: Дейкстра в полной версии (с очередью с приоритетом) — это база, которую ждут на профильных направлениях.
Коллеги, а какой подход вы чаще всего берёте за основу на уроках? Делитесь в комментариях — интересно собрать разные педагогические практики. А ученикам — попробуйте реализовать все три варианта на одном и том же файле: это лучший способ почувствовать разницу.