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

• Граф — набор вершин и соединяющих их рёбер. Вершины на КЕГЭ всегда пронумерованы натуральными числами.
• Ориентированный граф (орграф) — рёбра имеют направление: ребро из $L$ в $M$ не даёт права пройти из $M$ в $L$.
• Взвешенный граф — каждому ребру приписано число, его вес. В задании 23 вес — положительное вещественное число, а длина пути — сумма весов входящих в него рёбер.
• Ациклический граф — в нём нельзя, идя по стрелкам, вернуться в ту же вершину. Именно ацикличность делает подсчёт количества путей конечной задачей: в графе с циклом путей было бы бесконечно много.
• Путь — последовательность вершин, в которой каждая следующая соединена с предыдущей ребром нужного направления.

Каждая строка файла — одно ребро: L M W. Числа разделены «произвольным ненулевым количеством пробелов и/или табуляций», поэтому единственный правильный способ разобрать строку — split() без аргументов: он сам съедает любое количество любых пробельных символов.

graph = {}
for line in open('23.txt'):
    parts = line.split()
    if len(parts) != 3:
        continue
    a, b, w = int(parts[0]), int(parts[1]), float(parts[2])
    graph.setdefault(a, []).append((b, w))

Проверка len(parts) != 3 нужна ради последней пустой строки файла — без неё программа падает на int(parts[0]). Словарь graph хранит список смежности: для каждой вершины — список пар «куда» и «сколько стоит». Ребро добавляется только один раз, потому что граф ориентированный.

Идея алгоритма Дейкстры: держим для каждой вершины $v$ текущую оценку $d[v]$ — длину самого короткого известного пути из старта. В начале $d[1] = 0$, у остальных вершин оценки нет. Дальше повторяем один шаг: берём непросмотренную вершину с наименьшей оценкой, объявляем её оценку окончательной и «расслабляем» все исходящие из неё рёбра:

Почему первую же вынутую вершину можно считать готовой: веса положительны, поэтому любой другой путь до неё пройдёт через вершину с оценкой не меньше текущей и станет только длиннее. Именно на этом условии — веса неотрицательны — алгоритм и держится; в задании 23 оно записано в условии словами «положительное вещественное число».

«Взять вершину с наименьшей оценкой» быстрее всего делает куча — модуль heapq из стандартной библиотеки Python:

import heapq

INF = float('inf')
dist = {1: 0.0}
queue = [(0.0, 1)]
while queue:
    d, v = heapq.heappop(queue)
    if d > dist.get(v, INF):
        continue
    for u, w in graph.get(v, []):
        if d + w < dist.get(u, INF):
            dist[u] = d + w
            heapq.heappush(queue, (d + w, u))

print(int(dist[100]))

int() для положительного числа — это и есть целая часть, отбрасывание дробной части: int(7.5) даёт 7. Не пишите round() — он даст 8 и обнулит задание.

Если куча и «непросмотренные вершины» кажутся лишней конструкцией на экзамене, есть код короче и его почти невозможно написать неправильно. Рёбер по условию не больше 200, значит и вершин на любом пути не больше 201. Просто расслабляем все рёбра подряд столько раз, сколько рёбер в файле, пока хоть что-то меняется:

INF = float('inf')
dist = {1: 0.0}
for _ in range(len(edges)):
    changed = False
    for a, b, w in edges:
        if dist.get(a, INF) + w < dist.get(b, INF):
            dist[b] = dist[a] + w
            changed = True
    if not changed:
        break

print(int(dist[100]))

Это алгоритм Беллмана — Форда. Он медленнее Дейкстры, но при 200 рёбрах разница незаметна: 200 × 200 = 40 000 операций, миллисекунды. На демоверсии 2027 года оба варианта дают одинаковый ответ.

Пусть $P[v]$ — количество различных путей из вершины $v$ в конечную вершину $T$. Тогда $P[T] = 1$ (пустой путь), а для любой другой вершины путь начинается с одного из исходящих рёбер:

Веса здесь не участвуют вообще. Ацикличность гарантирует, что рекурсия закончится: по стрелкам нельзя вернуться назад, поэтому каждая вершина считается ровно один раз. Кэш count превращает экспоненциальный перебор в линейный по числу рёбер:

count = {}

def paths(v):
    if v == 100:
        return 1
    if v in count:
        return count[v]
    count[v] = sum(paths(u) for u, w in graph.get(v, []))
    return count[v]

print(paths(1))

Тупик обрабатывается сам собой: если из вершины не выходит ни одного ребра, sum по пустому списку даёт 0 — путей из неё в конец нет. Целые числа в Python не переполняются, поэтому ответ в миллиарды писать можно как есть.

Формулировка плана перечисляет обе задачи через запятую, значит вариант вправе спросить любую. Хорошая новость: обе решаются одной и той же заготовкой — «прочитать файл в список смежности, а потом посчитать по вершинам». Отличается только то, что накапливается: в первой задаче — минимум суммы весов, во второй — сумма количеств. Поэтому держите в голове один шаблон чтения файла и две короткие концовки к нему.

Граф задан таким файлом. Формат тот же, что в задании 23: номер вершины, номер вершины, вес ребра.

1  2  4.0
1  3  1.5
3  2  1.2
2  5  2.5
3  4  6.0
4  5  1.0
2  4  3.0

Вопрос: целая часть длины кратчайшего пути из вершины 1 в вершину 5.

Из вершины 1 выходят два ребра — в 2 (вес 4) и в 3 (вес 1,5). Считаем оценки по Дейкстре, каждый раз выбирая наименьшую из неокончательных:

d[1] = 0     -> расслабляем 1->2 (4.0) и 1->3 (1.5)
d[3] = 1.5   -> 3->2: 1.5 + 1.2 = 2.7 < 4.0, обновляем
                3->4: 1.5 + 6.0 = 7.5
d[2] = 2.7   -> 2->5: 2.7 + 2.5 = 5.2
                2->4: 2.7 + 3.0 = 5.7 < 7.5, обновляем
d[5] = 5.2   -> вершина 5 вынута из кучи, ответ готов
d[4] = 5.7   (уже не влияет: 5.7 + 1.0 = 6.7 > 5.2)

Кратчайший путь — $1 \to 3 \to 2 \to 5$ с длиной $1{,}5 + 1{,}2 + 2{,}5 = 5{,}2$. Целая часть — 5.

Проверка здравым смыслом: прямой путь $1 \to 2 \to 5$ даёт $4 + 2{,}5 = 6{,}5$, а путь через вершину 4 — не меньше 6,7. Ответ 5,2 меньше обоих, но больше веса самого лёгкого ребра из вершины 1 (1,5) — значит, в правдоподобных границах. Заметьте главное: жадный выбор «пойти по самому дешёвому ребру и всё» тут случайно сработал, а вот жадный выбор «пойти по самому дешёвому ребру из вершины 3» (это $3 \to 2$) дальше уже не гарантирует ничего — работает только полная процедура Дейкстры.

Веса здесь не нужны, поэтому оставим только пары вершин:

1 2
1 3
2 4
3 4
2 5
3 5
4 5
4 6
5 6

Вопрос: сколько существует различных путей из вершины 1 в вершину 6. Считаем $P[v]$ от конца к началу — от вершины с наибольшим номером к вершине 1 (в этом графе стрелки всегда идут от меньшего номера к большему, поэтому такой порядок и есть топологический):

P[6] = 1                          (конечная вершина)
P[5] = P[6]               = 1
P[4] = P[5] + P[6] = 1 + 1 = 2
P[3] = P[4] + P[5] = 2 + 1 = 3
P[2] = P[4] + P[5] = 2 + 1 = 3
P[1] = P[2] + P[3] = 3 + 3 = 6

Ответ — 6. Проверяем перечислением, благо граф крошечный: 1→2→4→5→6, 1→2→4→6, 1→2→5→6, 1→3→4→5→6, 1→3→4→6, 1→3→5→6. Ровно шесть.

Обратите внимание на вершину 4: путь 1→2→4→5→6 и путь 1→2→4→6 различаются только хвостом после вершины 4, и динамика считает этот хвост один раз — в значении $P[4] = 2$. Именно поэтому метод работает и на графе с тысячей вершин, где путей триллионы.

Приложенный к демоверсии файл содержит 200 строк — ровно верхняя граница из условия. Номера вершин доходят до 998, но реально в файле встречаются только 50 различных вершин, веса лежат в диапазоне от 44,0 до 9988,0. Руками такой граф не разобрать — и в этом смысл перевода задания в «компьютерные».

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

import heapq

graph = {}
for line in open('23.txt'):
    parts = line.split()
    if len(parts) != 3:
        continue
    a, b, w = int(parts[0]), int(parts[1]), float(parts[2])
    graph.setdefault(a, []).append((b, w))

INF = float('inf')
dist = {1: 0.0}
queue = [(0.0, 1)]
while queue:
    d, v = heapq.heappop(queue)
    if d > dist.get(v, INF):
        continue
    for u, w in graph.get(v, []):
        if d + w < dist.get(u, INF):
            dist[u] = d + w
            heapq.heappush(queue, (d + w, u))

print(int(dist[100]))   # 10971

Программа печатает 10971 — это и есть ответ демоверсии. Кратчайший путь проходит через двенадцать рёбер:

1 → 173 → 975 → 625 → 312 → 633 → 825 → 96 → 59 → 698 → 221 → 56 → 100
2034 + 278 + 44 + 193 + 93 + 1508 + 1112 + 443 + 1987 + 459 + 2547 + 273 = 10971

Проверка здравым смыслом: из вершины 1 выходит 12 рёбер, и самое лёгкое из них весит меньше 2034 — то есть жадный первый шаг кратчайшего пути не совпадает с самым дешёвым ребром. Это типичная картина: если ваша программа выдаёт заметно меньшее число, скорее всего вы случайно сделали граф неориентированным и «прошли» по ребру против стрелки.

Разберитесь с терминами: вершина, ребро, ориентированное ребро, вес, путь, цикл, ациклический граф. Нарисуйте на бумаге пять маленьких графов по 5–7 вершин и для каждого выпишите список смежности. Научитесь по списку строк «L M W» восстанавливать картинку и обратно — по картинке писать файл.

Напишите одну функцию чтения файла и доведите её до автоматизма: split(), проверка длины, int для вершин и float для веса, setdefault для словаря. Прогоните её на типовом примере из демоверсии и убедитесь, что получаются ровно восемь рёбер и шесть вершин.

Напишите Дейкстру с heapq и вариант с релаксацией всех рёбер — и убедитесь, что на одном и том же файле они дают одинаковый ответ. Отдельно напишите подсчёт путей с кэшем. Проверяйте себя на графах из 5–8 вершин, где ответ можно пересчитать перечислением.

Цель — уложиться в 12 минут: 2 минуты на чтение условия, 5 на код, 2 на запуск и 3 на проверку. Заведите шаблон: чтение файла + пустое место под концовку. На каждом прогоне отдельно проверяйте, что взяли целую часть, а не округлили, и что подставили номера вершин из своего условия.