Задание 23: Графы: кратчайший путь и число путей

Теория к заданию № 23 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

Что проверяет задание 23

Что проверяет
Новое содержание № 23 в КИМ-2027: алгоритмические задачи на графах — построение оптимального пути между вершинами, количество различных путей в ориентированном ациклическом графе.
Баллы
до 1 балл из 29 первичных
Уровень
повышенный
Время
около 12 минут (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат
краткий ответ; нужен компьютер (программа, таблица или файл)

Правило и теория

  • Ориентированный ациклический граф (DAG) не имеет циклов, его вершины можно упорядочить так, что все рёбра идут «вперёд» (топологический порядок).
  • Кратчайший путь в DAG: d(start) = 0, затем по топологическому порядку d(v) = min(d(u) + w(u, v)) по всем рёбрам u → v.
  • Число путей: N(start) = 1, N(v) = сумма N(u) по рёбрам u → v.
  • Файл с рёбрами «L M W» читают в список смежности: graph[L].append((M, W)).
  • Для графов с неотрицательными весами общего вида кратчайший путь ищут алгоритмом Дейкстры (heapq в Python).

Приём решения по шагам

  1. Прочитай файл и построй список смежности (и входящие рёбра, если удобнее).
  2. Найди топологический порядок (алгоритм Кана: вершины с нулевой входящей степенью).
  3. Пройди вершины по порядку и обнови расстояния или количества путей.
  4. Выведи значение для целевой вершины в требуемом формате (целое/округление по условию).

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

Задание выполняется с использованием прилагаемого файла. В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число W — номера вершин графа и вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер графа. Две вершины графа не могут быть соединены более чем одним ребром. Найди и запиши в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 2375. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов входящих в него рёбер. Вершины графа пронумерованы подряд натуральными числами от 1 до 2375; 0 < W ≤ 10 000. Значения в строке разделены произвольным ненулевым количеством пробелов и/или символов табуляции.

Файл к заданию: 23.txt

Показать ответ и разбор

Ответ: 11305

В графе 2375 вершин и 9500 рёбер. Граф ациклический, поэтому кратчайшие расстояния можно считать динамикой в порядке топологической сортировки (или алгоритмом Дейкстры — веса положительные). Расстояние до вершины 2375: 11305.6100, целая часть — 11305. Ответ: 11305.

Карточка банка «Ранга» informatics-23-8 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Задание выполняется с использованием прилагаемого файла. В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число W — номера вершин графа и вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер графа. Две вершины графа не могут быть соединены более чем одним ребром. Найди и запиши в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 2674. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов входящих в него рёбер. Вершины графа пронумерованы подряд натуральными числами от 1 до 2674; 0 < W ≤ 10 000. Значения в строке разделены произвольным ненулевым количеством пробелов и/или символов табуляции.

Файл к заданию: 23.txt

Показать ответ и разбор

Ответ: 20759

В графе 2674 вершин и 8022 рёбер. Граф ациклический, поэтому кратчайшие расстояния можно считать динамикой в порядке топологической сортировки (или алгоритмом Дейкстры — веса положительные). Расстояние до вершины 2674: 20759.2300, целая часть — 20759. Ответ: 20759.

Карточка банка «Ранга» informatics-23-9 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Типичные ошибки

  • Обходят вершины не в топологическом порядке — значения обновляются раньше, чем найдены предшественники.
  • Путают направление ребра (L → M, а не M → L).
  • Для числа путей суммируют веса вместо количеств.
  • Неверно округляют вещественный ответ (нужна целая часть или округление — читай условие).

Тренироваться: 30 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 23

Кабинет ученика · Разбор задания 23: 10 примеров

Частые вопросы о задании 23

Сколько баллов дают за задание 23 ЕГЭ по информатике?
До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.
Сколько времени тратить на задание 23?
Примерное время выполнения по спецификации ФИПИ — 12 минут; на весь экзамен отводится 235 минут.
Что проверяет задание 23?
Новое содержание № 23 в КИМ-2027: алгоритмические задачи на графах — построение оптимального пути между вершинами, количество различных путей в ориентированном ациклическом графе.
Где потренироваться на задании 23?
В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.