Задание 23 · ЕГЭ, информатика 2027
Алгоритмические задачи с графами
Количество путей и кратчайший путь в ориентированном графе.
Простыми словами
Схема дорог с односторонним движением. Сколько разных маршрутов из А в И? Какой из них самый короткий? Обе задачи решаются одним движением по схеме слева направо: для каждого пункта записываем число — сумму (для числа путей) или минимум (для длины пути).
Тематика номера 23 изменена в 2027 году. Раньше под этим номером был анализ хода исполнения алгоритма — материалы прошлых лет по номеру 23 к нынешней теме отношения не имеют.
Количество путей
где — число путей из начальной вершины в . В начальную вершину — один «пустой» путь: . Считать нужно по порядку, чтобы к моменту обработки вершины все её предшественники были уже посчитаны.
- (в них ведёт только А).
- ; .
- ; ; .
Е нельзя считать раньше Д: из Д в Е есть стрелка. Ищите «вертикальные» стрелки внутри одного столбца — их чаще всего пропускают.
Через вершину и в обход
«Через Е и Ж» — три множителя: А→Е, Е→Ж, Ж→И. «Не через Е и не через Ж» — обнулить обе вершины.
Кратчайший путь
То же движение по вершинам, но вместо суммы — минимум:
Дуги: А→Б 3, А→В 1, В→Б 1, Б→Г 2, В→Г 5. Кратчайший путь из А в Г?
- ; .
- .
- — путь А→В→Б→Г.
Где теряют балл: двигаются против стрелки; при «через вершину» складывают части вместо умножения; для кратчайшего пути берут прямую дугу, не проверив обход.
Где эта тема разобрана подробно
Готовые работы по теме
Собраны заранее — одним нажатием: распечатать с ключом, раздать ученикам ссылкой или QR-кодом, поменять настройки. Номер набора постоянный: по этой ссылке всегда та же работа.
теория этой темы, 8 заданий по подтемам и ключ — файлом DOCX, который можно править под себя.
Прохождение онлайн
Имя ученика никуда не отправляется: он вводит только номер по списку, а таблицу «номер → фамилия» видите только вы.
Классы, выданные работы и результаты учеников по кодам — в журнале учителя: без регистрации, хранится только на этом компьютере.