Задание 23 ЕГЭ по информатике: Кратчайший путь в графе
Место освободилось после переезда анализа алгоритма на тринадцатый номер, и его занял граф. В текстовом файле лежит список рёбер с весами, и нужно найти длину кратчайшего пути между двумя вершинами или число различных путей в ориентированном ациклическом графе. Без программы такой объём данных не разобрать.
Страница обновлена 5 сентября 2026
Коротко о задании
| Уровень сложности | повышенный |
|---|---|
| Максимальный балл | 1 балл |
| Форма ответа | целое число |
| Сколько минут закладывать | 12 минут |
| Коды кодификатора |
|
Проект демоверсии
Структура по проекту демоверсии ФИПИ 2027; официальную версию ФИПИ публикует в ноябре. По проекту спецификации ФИПИ 2027 (обсуждение до 30 сентября 2026). Число заданий, баллы и продолжительность прежние, переписаны формулировки номеров 10, 13, 23 и форма записи ответа в 27.
Источник — ФИПИ, проект спецификации КИМ ЕГЭ 2027 по информатике (28 августа 2026).
Как решать
- Прочитайте файл и сложите граф в словарь: из какой вершины в какую и с каким весом.
- Для кратчайшего пути возьмите алгоритм Дейкстры или разверните динамику по порядку вершин.
- Для подсчёта путей идите по вершинам в топологическом порядке, складывая пути предшественников.
- Проверьте программу на маленьком графе, нарисованном на черновике.
- Возьмите от ответа целую часть, если веса вещественные.
Типичные ошибки
- Считают рёбра двусторонними, хотя граф ориентированный.
- Обрывают чтение файла на последней строке без перевода строки.
- Округляют длину пути вместо того, чтобы взять целую часть.
Нарисуйте на черновике граф из пяти вершин и посчитайте ответ руками: почти все ошибки в этом номере видны уже на таком размере.