Задание 23 ЕГЭ по информатике: кратчайший путь и число путей в графе

Задание 23 ЕГЭ по информатике в 2027 году проверяет умение решать алгоритмические задачи на графах: по списку рёбер из файла нужно найти длину кратчайшего пути или количество различных путей между вершинами ориентированного ациклического графа. Решают его программой, которая читает граф из файла и считает ответ по вершинам.

Как решать

Граф в файле задан списком рёбер: в каждой строке номер начальной вершины, номер конечной и, если нужно, вес ребра. Числа могут разделяться любым количеством пробелов и табуляций, поэтому строку разбивают методом split() без аргументов. Номера вершин идут не подряд, поэтому граф хранят в словаре «вершина — список рёбер».

В ориентированном ациклическом графе нет циклов, и значение для вершины можно вычислить через значения соседей. Длина кратчайшего пути до вершины v равна наименьшей сумме «расстояние до u плюс вес ребра u → v» по всем рёбрам, входящим в v. Количество путей из вершины v в конечную вершину равно сумме таких количеств для всех вершин, в которые ведут рёбра из v; для самой конечной вершины оно равно 1.

Проще всего записать это рекурсивной функцией с @lru_cache: она сама вычислит значения в нужном порядке. Другой способ — проходить по всем рёбрам и уменьшать расстояния, пока они меняются, как в алгоритме Беллмана — Форда; при 200 рёбрах это занимает доли секунды.

Веса рёбер вещественные, поэтому расстояния храните как float и в конце берите целую часть функцией int(). Количество путей растёт очень быстро, но целые числа в Python не переполняются.

Небольшой граф можно решить вручную: расположите вершины по порядку и подпишите у каждой найденное расстояние или число путей. Этот приём удобен и для проверки программы на примере из условия.

Примеры с решением

Пример 1

Ациклический ориентированный взвешенный граф задан списком рёбер. В каждой строке записаны номера двух вершин L и M и вес W ребра, ведущего из L в M:

1   8   2.5
1   15  6.0
8   15  3.0
8   42  7.5
15  42  1.5
15  100 12.0
42  100 4.4
8   100 13.0
42  77  0.5
77  100 3.75

Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100. Длина пути — сумма весов рёбер, составляющих путь.

Решение на Python

edges = [
    (1, 8, 2.5), (1, 15, 6.0), (8, 15, 3.0), (8, 42, 7.5), (15, 42, 1.5),
    (15, 100, 12.0), (42, 100, 4.4), (8, 100, 13.0), (42, 77, 0.5), (77, 100, 3.75),
]
dist = {1: 0.0}
changed = True
while changed:                               # простая релаксация рёбер до устойчивости
    changed = False
    for a, b, w in edges:
        if a in dist and dist[a] + w < dist.get(b, float('inf')):
            dist[b] = dist[a] + w
            changed = True
print(int(dist[100]))

Ответ: 11

Считаем расстояния от вершины 1: до 8 — 2,5; до 15 — min(6,0; 2,5 + 3,0) = 5,5; до 42 — min(2,5 + 7,5; 5,5 + 1,5) = 7,0; до 77 — 7,0 + 0,5 = 7,5. До вершины 100 выбираем наименьшее из 5,5 + 12,0, 7,0 + 4,4, 2,5 + 13,0 и 7,5 + 3,75: это 11,25 по пути 1 → 8 → 15 → 42 → 77 → 100. Целая часть — 11.

Пример 2

Задание выполняется с использованием прилагаемого файла. В файле описан ациклический ориентированный граф: в каждой строке записаны номера двух вершин L и M, что означает ребро из L в M. Числа в строке разделены одним или несколькими пробелами или табуляциями, вершины пронумерованы не подряд, номера не превышают 1000.

Определите количество различных путей из вершины 1 в вершину 100.

Файл данных: 23_ex2.txt — 150 строк, 1,3 КБ. Первые строки файла:

771	728
771 	 548
728	674
659	239
771	532
210  500
43  409
255 	 316

Решение на Python

from functools import lru_cache

graph = {}
for line in open('23_ex2.txt'):
    parts = line.split()                     # любое число пробелов и табуляций
    if len(parts) >= 2:
        a, b = int(parts[0]), int(parts[1])
        graph.setdefault(a, []).append(b)


@lru_cache(None)
def paths(v):
    """Число различных путей из v в вершину 100."""
    if v == 100:
        return 1
    return sum(paths(u) for u in graph.get(v, []))


print(paths(1))

Ответ: 29710281312

В файле 150 рёбер и 59 вершин, а путей из 1 в 100 больше 29 миллиардов, поэтому перебирать их по одному нельзя. Функция paths(v) с запоминанием вычисляет число путей из каждой вершины один раз, и программа работает доли секунды.

Пример 3

Задание выполняется с использованием прилагаемого файла. В файле описан ациклический ориентированный взвешенный граф: в каждой строке записаны два натуральных числа L и M и положительное вещественное число W — вес ребра, ведущего из вершины L в вершину M. Две вершины соединены не более чем одним ребром. Числа в строке разделены одним или несколькими пробелами или табуляциями, вершины пронумерованы не подряд, номера не превышают 1000.

Найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100. Длина пути — сумма весов рёбер, составляющих путь. Существование хотя бы одного такого пути гарантировано условием.

Файл данных: 23_ex3.txt — 180 строк, 2,5 КБ. Первые строки файла:

648 327 39.57
812 62	21.9
713	59 12.1
791	273 17.4
855 	146 43.68
723 592   9.2
161  393 11.4
135 	302 5.5

Решение на Python

from functools import lru_cache

edges = {}
for line in open('23_ex3.txt'):
    parts = line.split()                     # пробелы и табуляции в любом количестве
    if len(parts) == 3:
        a, b, w = int(parts[0]), int(parts[1]), float(parts[2])
        edges.setdefault(a, []).append((b, w))


@lru_cache(None)
def dist(v):
    """Длина кратчайшего пути из v в вершину 100 (граф без циклов)."""
    if v == 100:
        return 0.0
    return min((w + dist(u) for u, w in edges.get(v, [])), default=float('inf'))


print(int(dist(1)))

Ответ: 230

В файле 180 рёбер и 70 вершин. Функция dist(v) с запоминанием возвращает длину кратчайшего пути из вершины v в вершину 100: для каждого ребра v → u она складывает вес ребра и dist(u) и берёт наименьшую сумму. Для вершины 1 получается 230,46, целая часть — 230. Тот же результат даёт повторная релаксация рёбер, которой удобно проверить ответ.

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

Потренироваться на тренажёре

Частые вопросы

Что изменилось в задании 23 в 2027 году?

По проекту спецификации 2027 года задание 23 проверяет решение задач на графах: построение оптимального пути и подсчёт различных путей в ориентированном ациклическом графе. Задача про количество программ исполнителя перешла в задание 13.

Как прочитать файл, если числа разделены табуляциями?

Используйте `line.split()` без аргументов: метод делит строку по любым пробельным символам и не создаёт пустых элементов.

Нужно ли знать алгоритм Дейкстры?

Для ациклического графа достаточно расчёта по вершинам или повторного прохода по рёбрам. Алгоритм Дейкстры тоже даёт верный ответ при неотрицательных весах, но программа с ним длиннее.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 22 и задание 24.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.