В задании 23 ЕГЭ по информатике 2027 года дают текстовый файл: в каждой строке записано ребро графа, то есть откуда, куда и сколько стоит пройти. По проекту демоверсии ФИПИ 2027 спрашивают одно из двух: длину кратчайшего пути между двумя вершинами (в ответ идёт её целая часть) или количество различных путей в графе без циклов. Задание повышенного уровня, стоит 1 балл, на него отводят около 12 минут, и решается оно только программой.
Нумерация ЕГЭ-2027. Это новое задание. Прежнее задание 23 (число программ) теперь под номером 13.
Чему научишься. После разбора сможешь:
- прочитать файл с рёбрами в словарь, не споткнувшись о пробелы, табуляции и дробные веса;
- найти длину кратчайшего пути и перепроверить её вторым алгоритмом;
- посчитать число путей в графе без циклов, не перебирая сами пути;
- встроить в программу дополнительное условие: через вершину, в обход вершины, не больше K рёбер.
Что изменилось в 2027
ФИПИ переставил три задания по цепочке. Анализ хода алгоритма, который раньше стоял на 23-м месте, переехал на 13-е: его разбор теперь живёт на странице задания 13 (бывшего 23). Маски подсети ушли с 13-го места на 10-е, они разобраны здесь. Поиск в текстовом редакторе, бывшее задание 10, из экзамена убрали совсем. Освободившийся номер 23 занял граф.
Пока всё это проект: ФИПИ утверждает документы в ноябре 2026 года. Структура экзамена при этом прежняя, 27 заданий и 235 минут, так что для нынешних 11-классников, которые сдают ЕГЭ весной 2027, меняется содержание одного номера, а не правила игры.
Теория: граф, рёбра, вес, ориентация
Представь карту дорог между посёлками. Посёлки на ней точки, дороги линии между ними, у каждой дороги подписано время в пути. Если дорога односторонняя, на ней стрелка. Ровно такую картину описывает файл задания, только посёлки названы номерами.
- Вершина: точка на карте, у нас номер от 1 до 1000.
- Ребро: связь между двумя вершинами, одна строка файла.
- Ориентированный граф: у рёбер есть направление, по ребру «из L в M» обратно не пройти.
- Вес: число на ребре (расстояние, время, цена). Длина пути равна сумме весов его рёбер.
- Цикл: маршрут, который по стрелкам возвращается в ту же вершину.
- Ациклический граф: граф, где циклов нет. В задании 23 граф именно такой, и это сильно упрощает решение.
Возьмём маленький файл из восьми строк. Каждая строка читается как «из вершины L ведёт ребро в вершину M весом W»:
100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
Из вершины 3 в вершину 42 ведут четыре пути: прямое ребро длиной 11.0, через вершину 15 (4.5 + 6.0 = 10.5), через вершины 8 и 20 (2.0 + 7.5 + 1.0 = 10.5) и через вершины 8 и 15 (2.0 + 1.5 + 6.0 = 9.5). Кратчайший последний, хотя в нём больше всего рёбер; целая часть его длины 9. Прямое ребро оказалось самым длинным вариантом, поэтому правило «иду туда, где ближе к цели» здесь не работает: программа обязана сравнить все варианты.
Сам формат и пример условия есть в проекте демоверсии ФИПИ 2027.
Если графы тебе в новинку, начни с задания 1 ЕГЭ: там та же модель, только маленькая и решается без программы.
Как прочитать файл с рёбрами
Программа должна быстро отвечать на вопрос «из вершины X куда можно шагнуть и за сколько». Для этого строят словарь смежности: ключ словаря номер вершины, значение список пар «куда, вес». Для примера выше у вершины 3 получится список [(15, 4.5), (8, 2.0), (42, 11.0)].
В файле три ловушки, и каждая ломает верную по смыслу программу. Номера вершин идут не подряд: вершин может быть тридцать, а номера у них 691, 893, 994, так что список на 1001 ячейку почти весь пустой, и нужен словарь. Между числами стоит то один пробел, то несколько, то табуляция, поэтому строку режем split() без аргументов. Вес дробный, читаем его через float.
from collections import defaultdict
граф = defaultdict(list) # вершина -> список пар (куда, вес)
рёбра = [] # те же рёбра плоским списком, для проверки
for строка in open('23.txt'):
части = строка.split() # любые пробелы и табуляции
if len(части) < 3: # пустая строка в конце файла
continue
откуда, куда, вес = int(части[0]), int(части[1]), float(части[2])
граф[откуда].append((куда, вес))
рёбра.append((откуда, куда, вес))defaultdict(list) из модуля collections ведёт себя как обычный словарь, но при обращении к отсутствующему ключу сам заводит пустой список. У вершины, из которой не выходит ни одного ребра (в примере это 9), граф[9] вернёт [], а не ошибку. Плоский список рёбра пригодится для проверочного алгоритма. Про словари подробнее в статье про структуры данных в Python.
Контрольный вопрос.
В файле задания 23 числа в строке разделены произвольным количеством пробелов и символов табуляции вперемешку. Каким способом строку нужно разбирать, чтобы разделители любого вида обработались правильно?
Подсказка: Подумайте, какой из вариантов не требует знать заранее, какой именно разделитель встретится в конкретной строке.
Контрольный вопрос.
Программа строит словарь смежности строкой
граф[куда].append((откуда, вес))Файл прочитан целиком, ошибок не возникает, но найденные пути оказываются неверными. Что здесь не так?
Подсказка: Вспомните, что означает строка файла «L M W»: в какую сторону ведёт ребро и от какой вершины мы будем искать соседей.
Как запустить. Скачанный файл приходит с длинным именем из букв и цифр, это нормально. Переименуй его в
23.txtи положи в ту же папку, где сохранена программа:open('23.txt')ищет файл рядом с собой. Программу открой в IDLE (File → New File), сохрани и нажми F5. В выводе должно появиться одно целое число без точки.
Контрольный вопрос.
Программа со строкой
open('23.txt')остановилась с сообщениемFileNotFoundError. Файл задания скачан и лежит в папке «Загрузки», а сама программа сохранена на рабочем столе. Что нужно исправить?Подсказка: Короткое имя в кавычках означает «файл рядом со мной». Спросите себя, где для программы находится это «рядом».
Тип 1. Кратчайший путь
Способ 1: рекурсия с запоминанием
Вопрос удобнее перевернуть. Не «куда идти из старта», а «сколько стоит дойти до финиша из вершины X». У самого финиша это ноль. У любой другой вершины это наименьшая из сумм «вес ребра + сколько стоит дойти от соседа». Функция вызывает сама себя для соседей, те для своих, и так до финиша.
from functools import cache
@cache
def лучший(вершина, финиш):
if вершина == финиш:
return 0.0
ответ = float('inf') # тупик: дойти нельзя
for сосед, вес in граф[вершина]:
ответ = min(ответ, вес + лучший(сосед, финиш))
return ответ
print(int(лучший(3, 42)))9Декоратор @cache запоминает ответ для каждой вершины. Без него одна и та же вершина пересчитывалась бы на каждом пути через неё, а путей в реальном файле бывают миллионы. Это тот же приём, что в задании 13 и в задании 16. @cache появился в Python 3.9; на старой версии пиши from functools import lru_cache и @lru_cache(None).
Рекурсия верна только на графе без циклов: иначе функция пойдёт по кругу и упадёт с RecursionError. В тексте задания стоит слово «ациклический», значит, можно. Глубину рекурсии поднимать не нужно: в файле до 200 строк, в пути не больше 200 рёбер, а Python разрешает около 1000 вложенных вызовов.
Способ 2: алгоритм Дейкстры
Дейкстра идёт от старта. Для каждой вершины держим лучшее найденное расстояние и на каждом шаге достаём из очереди самую близкую из ещё не обработанных вершин, а потом пробуем улучшить расстояния до её соседей. Очередь держит модуль heapq: heappop всегда отдаёт наименьший элемент. Алгоритм работает на любом графе с положительными весами, в том числе с циклами.
import heapq
def кратчайший(граф, старт, финиш):
расстояние = {старт: 0.0}
очередь = [(0.0, старт)]
while очередь:
d, вершина = heapq.heappop(очередь)
if d > расстояние.get(вершина, float('inf')):
continue # устаревшая запись
for сосед, вес in граф[вершина]:
новое = d + вес
if новое < расстояние.get(сосед, float('inf')):
расстояние[сосед] = новое
heapq.heappush(очередь, (новое, сосед))
return расстояние.get(финиш)
print(int(кратчайший(граф, 3, 42)))9На примере ответ улучшается: сначала до вершины 42 известно только прямое ребро 11.0, а когда обработана вершина 15 (до неё 2.0 + 1.5 = 3.5), находится 9.5. Остановиться на первом найденном пути значит записать неверный ответ.
Проверка себя: Беллман-Форд
Проверить число на экзамене не у кого. Поэтому я учу решать задание двумя способами и сверять. Беллман-Форд проще всех: ни рекурсии, ни очереди, только повторные проходы по списку рёбер, пока расстояния улучшаются. Рекурсия считает от финиша, Дейкстра от старта, Беллман-Форд работает по плоскому списку. Ошибка одного почти никогда не повторится в другом.
def беллман_форд(рёбра, старт, финиш):
вершины = {x for р in рёбра for x in р[:2]}
расстояние = {v: float('inf') for v in вершины}
расстояние[старт] = 0.0
for _ in range(len(вершины) - 1):
изменилось = False
for откуда, куда, вес in рёбра:
if расстояние[откуда] + вес < расстояние[куда]:
расстояние[куда] = расстояние[откуда] + вес
изменилось = True
if not изменилось:
break
return расстояние[финиш]Больше про эти алгоритмы в обзоре основных алгоритмов на Python.
Целая часть: int вместо round
Считай в дробных числах до самого конца и только у готового ответа возьми int(...). round(9.5) даст 10, а задание просит целую часть, то есть 9. Округлять веса по дороге тоже нельзя: дробные части рёбер сложатся иначе.
Контрольный вопрос.
Кратчайший путь из стартовой вершины в финишную равен 7.5. В конце программы стоит строка
print(лучший(старт, финиш))Что появится в выводе и будет ли такой ответ засчитан?
Подсказка: Python печатает вещественное число как есть. Сравните это с тем, что именно просит записать в ответе условие задания.
Контрольный вопрос.
В файле задания 40 вершин, но их номера доходят до 1000. Ученик решил применить алгоритм Флойда и завести таблицу «каждая вершина с каждой» прямо по номерам вершин. Что произойдёт и что нужно сделать?
Подсказка: Оцените, сколько троек вершин переберёт алгоритм, если считать по номерам до 1000, и сравните с числом вершин, которые реально есть в файле.
Тип 2. Количество путей в графе без циклов
Перебрать пути по одному не выйдет: каждая развилка умножает их число, и на файле из 200 строк ответ придётся ждать часами. Сами пути нам и не нужны, нужно только их количество. Число путей из вершины X в финиш равно сумме чисел путей у вершин, куда из X ведут рёбра. У финиша оно равно единице.
from functools import cache
@cache
def путей(вершина, финиш):
if вершина == финиш:
return 1
ответ = 0
for сосед, вес in граф[вершина]:
ответ = ответ + путей(сосед, финиш)
return ответ
print(путей(3, 42))4Функция почти та же, что для кратчайшего пути, отличий три: у финиша 1 вместо 0.0, перед циклом 0 вместо бесконечности, в цикле сумма вместо минимума. Веса в этом вопросе не участвуют вовсе. Если ты решал бывшее задание 23 про число программ, приём тебе знаком: там тоже складывали количества, а не выписывали программы.
Второй способ для проверки идёт вперёд по топологическому порядку. Это очерёдность вершин, где каждая стоит после всех, из которых в неё ведут рёбра, как в списке дел: «купить продукты» раньше «приготовить ужин». Строим порядок так: берём вершину, в которую ничего не входит, ставим в очередь и «убираем» её рёбра; у соседей счётчик входящих рёбер уменьшается, и кто-то из них становится следующим. Если в порядок попали не все вершины, в графе цикл, и почти наверняка файл прочитан неправильно.
def путей_по_порядку(граф, рёбра, старт, финиш):
вершины = {x for р in рёбра for x in р[:2]}
вход = {в: 0 for в in вершины}
for откуда, куда, вес in рёбра:
вход[куда] += 1
очередь = [в for в in вершины if вход[в] == 0]
порядок = []
while очередь:
в = очередь.pop()
порядок.append(в)
for сосед, вес in граф[в]:
вход[сосед] -= 1
if вход[сосед] == 0:
очередь.append(сосед)
if len(порядок) != len(вершины):
print('В графе есть цикл: файл прочитан не так')
путей = {в: 0 for в in вершины}
путей[старт] = 1
for в in порядок:
for сосед, вес in граф[в]:
путей[сосед] += путей[в]
return путей[финиш]Рекурсия считает «сколько путей отсюда до финиша», топологический проход считает «сколько путей от старта сюда». Числа обязаны совпасть.
Контрольный вопрос.
В программе подсчёта количества путей убрали строку
@cacheнад функцией. Логика подсчёта осталась верной. Что изменится?Подсказка: Ответ на вопрос «верно ли посчитает» и ответ на вопрос «дождёмся ли мы результата» здесь разные. Подумайте про оба.
Контрольный вопрос.
Программа построила топологический порядок для графа из файла. В графе 41 вершина, а в построенный порядок вошли только 38. О чём это говорит?
Подсказка: Вспомните, при каком условии вершина попадает в очередь кандидатов, и что мешает ей обнулиться, если она кого-то ждёт по кругу.
Вариации условия: через вершину, в обход, с ограничением
Составители любят добавить одно условие к базовому вопросу. Оно встаёт в одно из трёх мест программы.
- Через вершину N. Длина:
лучший(старт, N) + лучший(N, финиш). Количество путей: произведениепутей(старт, N) * путей(N, финиш), потому что каждый путь до N продолжается каждым путём после N. - В обход вершин. Пропусти при чтении файла строки, где запретная вершина стоит в начале или в конце ребра.
- Только рёбра весом не меньше L. Проверка
if вес >= Lвнутри цикла по соседям. - Не больше K рёбер. Третий параметр функции «сколько рёбер ещё можно пройти», при нуле путь невозможен.
- Сам путь. Функция возвращает пару «длина, кортеж вершин», дальше считаешь то, что просят.
Если в одной программе ты перестроил граф после первого подсчёта, @cache вернёт старые ответы. Запускай программу заново или вызови лучший.cache_clear().
Типичные ошибки
- Перепутано направление ребра: в словарь записали
граф[куда]вместограф[откуда]. Программа работает без ошибок, но ответ неверный. - Строку режут
split(' '): на двойном пробеле или табуляции в списке появляются пустые строки, иint('')падает. - Вес прочитан через
int: программа упадёт на7.5или потеряет дробную часть. OverflowError: cannot convert float infinity to integer: пути из старта в финиш не нашлось. Обычно перепутаны номера старта и финиша или опечатка при переписывании из условия.roundвместоint: при дробной части от 0.5 ответ выйдет на единицу больше.- Забыт
@cache: число получится верным, но программа не закончит работу до конца экзамена. - Повторные рёбра между одной парой вершин. В файлах этого разбора их нет, и условие ФИПИ их запрещает. Но если встретятся, оба алгоритма кратчайшего пути с ними справятся сами, а при подсчёте путей каждое ребро даст свой путь.
Задачи для тренировки
Во всех задачах файл устроен одинаково: в каждой строке два натуральных числа L и M (номера вершин, не больше 1000) и положительное вещественное число W (вес ребра из L в M, не больше 10 000). Строк не больше 200, числа разделены пробелами и табуляциями, граф ациклический, две вершины соединены не более чем одним ребром. Вершины пронумерованы не подряд. В ответ пиши одно целое число, если в задаче не сказано иначе.
Простые
Задание.
Файл к заданию: 23_s1.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 691 в вершину с номером 893. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Подсказка: Следите за направлением: строка «L M W» означает ребро ИЗ L В M, обратного ребра нет. Если добавить в граф ещё и обратное, путь из 691 в 893 может стать короче настоящего — а программа при этом не выдаст никакой ошибки.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_c1.txt
Найдите и запишите в ответе количество различных путей из вершины с номером 924 в вершину с номером 718. Существование хотя бы одного такого пути гарантируется. Пути считаются различными, если они отличаются хотя бы одним ребром.
Подсказка: Не пытайтесь перебрать сами пути от 924 до 718 — их бывают миллионы, программа не дождётся конца. Считайте не пути, а их количество: число путей из вершины складывается из чисел путей у тех вершин, куда из неё ведут рёбра.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_v1.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 518 в вершину с номером 80, проходящего через вершину с номером 968. Существование хотя бы одного такого пути гарантируется.
Подсказка: Путь через вершину складывается из двух участков: от старта до неё и от неё до финиша. Функцию переписывать не нужно — её достаточно вызвать дважды и сложить результаты.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_v3.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 533 в вершину с номером 985, не проходящего через вершину с номером 132. Существование хотя бы одного такого пути гарантируется.
Подсказка: Запрещённую вершину проще всего выбросить сразу при чтении файла: пропускайте каждую строку, где она стоит в начале или в конце ребра. Дальше программа та же.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Средние
Задание.
Файл к заданию: 23_v6.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 952 в вершину с номером 657, состоящего не более чем из 4 рёбер. Существование хотя бы одного такого пути гарантируется.
Подсказка: Функции нужен третий параметр — сколько рёбер ещё можно пройти. При каждом шаге он уменьшается на единицу, а при нуле, если финиш не достигнут, путь считается невозможным.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_v8.txt
Найдите кратчайший путь из вершины с номером 783 в вершину с номером 712 и запишите в ответе сумму номеров всех его промежуточных вершин (кроме 783 и 712). Гарантируется, что кратчайший путь единственный.
Подсказка: Пусть функция возвращает не одно число, а пару: длину и сам путь кортежем вершин. Сумму считайте только по промежуточным вершинам — без старта и финиша.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_v5.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 397 в вершину с номером 313, составленного только из рёбер, вес каждого из которых не меньше 150. Существование хотя бы одного такого пути гарантируется.
Подсказка: Ограничение на длину ребра проверяется там же, где перебираются соседи: неподходящее ребро просто пропускается. Сравнивайте с порогом вещественное число, а не округлённое.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_c8.txt
Найдите и запишите в ответе количество различных путей из вершины с номером 380 в вершину с номером 994. Существование хотя бы одного такого пути гарантируется. Пути считаются различными, если они отличаются хотя бы одним ребром.
Подсказка: Ноль в ответе означает, что до 994 не дошли ни разу. Проверьте две вещи: не перепутаны ли старт с финишем и правильно ли задана начальная единица — она ставится ровно одной вершине.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Сложные
Задание.
Файл к заданию: 23_h3.txt
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 825 в вершину с номером 500. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Подсказка: Первый найденный путь до 500 почти никогда не кратчайший. Убедитесь, что расстояние до вершины обновляется, если нашёлся более дешёвый путь, а не фиксируется при первом попадании.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_h6.txt
Найдите и запишите в ответе количество различных путей из вершины с номером 238 в вершину с номером 904. Существование хотя бы одного такого пути гарантируется. Пути считаются различными, если они отличаются хотя бы одним ребром.
Подсказка: Обязательно поставьте @cache над функцией. Без него каждая вершина будет пересчитываться заново на каждом пути через неё — это тот же перебор, только замаскированный, и на пути от 238 до 904 он не закончится.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Задание.
Файл к заданию: 23_dva_marshruta.txt
По одному и тому же графу найдите целые части длин двух кратчайших путей:
Задача решается заметно быстрее, если поиск пути оформлен отдельной функцией: тогда второй маршрут считается её повторным вызовом, а не копией кода. Такой функцией потом удобно пользоваться и на других заданиях блока.
В ответе запишите два числа через пробел в указанном порядке. Пример формата (числа выдуманы):
430 275.Подсказка: Соберите ответ из величин, которые программа считает по отдельности, и выведите их одной строкой через пробел — ровно в том порядке, как перечислено в условии.
✅ Готово, если: программа запускается без ошибок и выводит то, что просят в задании.
Ещё 28 задач с файлами и автопроверкой ответа — в курсе «Задание 23 ЕГЭ по информатике. Анализ графов» в личном кабинете. Если хочешь готовиться к ЕГЭ со мной, посмотри программу подготовки к ЕГЭ по информатике.
Задание 23 про графы точно будет в ЕГЭ 2027?
По проекту демоверсии ФИПИ 2027 года да: анализ графов стоит на 23-м месте. Окончательно документы ФИПИ утверждает в ноябре 2026 года, после этого разбор будет сверен заново.
Можно ли решить задание 23 без программы?
Нет. На графе из восьми рёбер путь видно глазами, но в задании файл до 200 строк и десятки вершин, поэтому нужна программа.
Можно ли решить задание 23 в Excel?
Нет, нужна программа. Спецификация относит задание к решаемым программой, а поиск кратчайшего пути и подсчёт путей по файлу из сотен рёбер в таблице не делаются.
Нужно ли знать алгоритм Дейкстры наизусть?
Достаточно шаблона на 15 строк, приведённого в этом разборе, и понимания, почему он работает. Для ациклического графа хватит ещё более короткой рекурсии с @cache, а Дейкстра пригодится как проверка.
Чем новое задание 23 отличается от старого?
Старое задание 23 было про исполнителя и число программ, в 2027 году оно стало заданием 13. Новое задание 23 даёт файл с рёбрами графа и спрашивает длину кратчайшего пути или число путей.
Сколько времени давать на задание 23?
По проекту спецификации ФИПИ 2027 года около 12 минут. Чтобы уложиться, чтение файла и обе функции стоит отработать заранее на тренировочных файлах, тогда на экзамене меняются только номера вершин.
Итог.
- Файл читаешь в словарь смежности:
split()без аргументов,floatдля веса.- Кратчайший путь ищешь рекурсией с
@cacheили Дейкстрой и сверяешь вторым способом; в ответint, неround.- Число путей считаешь суммой по соседям с запоминанием и проверяешь проходом по топологическому порядку.
🏠 На главную · ← Задание 22 · Навигатор по заданию 23 · Задание 24 →
