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

С 2027 года задание 23 посвящено анализу графов: к варианту прилагается файл с описанием ориентированного графа без циклов, и нужно найти длину оптимального (кратчайшего или самого длинного) пути между двумя вершинами или посчитать количество путей. Вершин и рёбер много — сотни и тысячи, поэтому задание решается программой: рекурсией с запоминанием результатов. Прежнее задание 23 про исполнитель и количество программ теперь стоит под номером 13.

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

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

Типичные формулировки

1. «Определите длину кратчайшего пути из вершины 1 в вершину 100».
2. «…пути, содержащего ровно 14 рёбер» или «…не менее 15 рёбер» — у функции появляется второй параметр, число оставшихся рёбер.
3. «Сколько существует различных путей из вершины 1 в вершину N?» — вместо минимума складываем.
4. «…путей, проходящих через вершину K» — путь разбивается на два участка, количества перемножаются.

Пошаговый метод

1. Прочитайте файл. Обычно каждая строка описывает одно ребро: начальная вершина, конечная вершина и вес. Сложите рёбра в словарь g[откуда] = [(куда, вес), ...].
2. Запишите формулу для одной вершины. Кратчайший путь из v в цель: 0, если v — цель; иначе минимум по всем рёбрам (v → u, w) величины w + f(u). Из вершины без выходящих рёбер цель недостижима — возвращаем «бесконечность».
3. Добавьте запоминание. Без @lru_cache(None) одна и та же вершина пересчитывается много раз, и программа может работать часами.
4. Для дополнительных условий добавьте параметр: число оставшихся рёбер, флаг «вершина K уже пройдена» и т. п.
5. Проверьте на маленьком графе, который можно посчитать вручную, затем запустите на файле.

Разбор примера

Граф задан рёбрами (начало, конец, вес): 1→2 (4), 1→3 (2), 3→2 (1), 2→4 (5), 3→4 (8), 2→5 (10), 3→5 (12), 4→5 (2). Найдите длину кратчайшего пути из 1 в 5 и количество путей из 1 в 5.

Кратчайший путь. Считаем от конца: f(5) = 0; f(4) = 2 + f(5) = 2; f(2) = min(5 + f(4), 10 + f(5)) = min(7, 10) = 7; f(3) = min(1 + f(2), 8 + f(4), 12 + f(5)) = min(8, 10, 12) = 8; f(1) = min(4 + f(2), 2 + f(3)) = min(11, 10) = 10. Путь 1 → 3 → 2 → 4 → 5.

Количество путей. p(5) = 1; p(4) = 1; p(2) = p(4) + p(5) = 2; p(3) = p(2) + p(4) + p(5) = 4; p(1) = p(2) + p(3) = 6.

Ответы: 10 и 6.

Код на Python

from functools import lru_cache

edges = [(1, 2, 4), (1, 3, 2), (3, 2, 1), (2, 4, 5), (3, 4, 8), (2, 5, 10), (3, 5, 12), (4, 5, 2)]
# на экзамене: for line in open('23.txt'): a, b, w = map(int, line.split())
g = {}
for a, b, w in edges:
    g.setdefault(a, []).append((b, w))

INF = float('inf')

@lru_cache(None)
def f(v, end):              # длина кратчайшего пути из v в end
    if v == end:
        return 0
    return min((w + f(u, end) for u, w in g.get(v, [])), default=INF)

@lru_cache(None)
def p(v, end):              # количество путей из v в end
    if v == end:
        return 1
    return sum(p(u, end) for u, w in g.get(v, []))

print(f(1, 5), p(1, 5))     # 10 6

Для пути с заданным числом рёбер добавьте параметр k: f(v, k) возвращает 0, если v — цель и k == 0, и «бесконечность», если k == 0, а цель не достигнута; иначе — минимум по рёбрам величины w + f(u, k − 1). Для самого длинного пути замените min на max, а «бесконечность» — на минус бесконечность.

Частые ошибки

• Нет запоминания. Рекурсия без @lru_cache(None) на большом графе работает очень долго. Обычный @lru_cache хранит только 128 значений — передавайте None.
• Недостижимая цель даёт 0. Если из вершины нет рёбер, путь не существует: для минимума возвращайте бесконечность, для количества — 0.
• Неверно прочитан файл: перепутаны начало и конец ребра или граф прочитан как неориентированный.
• Глубокая рекурсия. Для длинных путей увеличьте лимит: import sys; sys.setrecursionlimit(10000).

Потренируйтесь

Решите задания № 23 в банке и попробуйте задачи с проверкой кода. Идея подсчёта путей подробно разобрана в статье «Подсчёт путей и динамическое программирование». Следующее задание — задание 24: обработка символьных строк.