ЕГЭ по информатике 2026, задание 1: графы и кратчайший путь

Задание 1 проверяет умение читать информационную модель: схему дорог, карту, таблицу расстояний или формулу. В 2026 году линия не менялась. Это базовое задание на 1 балл, файл к нему не выдают, обычно хватает 3 минут.

Как выглядит условие

Чаще всего дают пункты и дороги между ними. Нужно найти длину кратчайшего пути между двумя пунктами или число пунктов на таком пути. Дороги бывают двусторонними и односторонними, с весами и без. Иногда вместо схемы — таблица, где пустая клетка или прочерк означает «дороги нет».

Конспект

1. Перенесите данные на черновик. Кружки — пункты, линии — дороги. Подпишите веса.

2. Если таблица, проверьте, симметрична ли она. Если нет — дороги односторонние.

3. Идите от старта. Для маленького графа достаточно перебрать маршруты без циклов. Цикл только удлиняет путь, его можно не рассматривать.

4. Записывайте не «красивый» путь, а минимальную уже найденную длину. Когда появляется более короткий, заменяйте.

5. Перечитайте вопрос: спрашивают длину, число дорог или число промежуточных пунктов? Это разные ответы.

6. Если путь должен проходить через заданный пункт, решайте две отдельные задачи: старт → обязательный пункт и он → финиш. Сумма кратчайших и есть ответ, если других ограничений нет.

Шаблон на Python

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

import heapq

edges = [
    ("A", "B", 4),
    ("A", "C", 2),
    ("B", "D", 5),
    ("C", "D", 1),
]
start, goal = "A", "D"

graph = {}
for a, b, w in edges:
    graph.setdefault(a, []).append((b, w))
    graph.setdefault(b, []).append((a, w))  # уберите строку, если дороги односторонние

dist = {start: 0}
heap = [(0, start)]
while heap:
    cur, node = heapq.heappop(heap)
    if cur != dist.get(node):
        continue
    if node == goal:
        break
    for nxt, w in graph.get(node, []):
        nd = cur + w
        if nd < dist.get(nxt, 10**9):
            dist[nxt] = nd
            heapq.heappush(heap, (nd, nxt))

print(dist.get(goal))

Если веса все равны 1, тот же ответ даст обход в ширину: длина пути — число рёбер.

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

• Пропущено направление стрелки на схеме.
• В ответ записано число вершин, хотя спрашивали длину.
• Посчитан путь «через все пункты», хотя такого условия нет.
• Для обязательной вершины взята сумма не кратчайших кусков.

Сверьте готовый ответ с одним явным маршрутом на черновике. Если программа выдала число, которого нет ни у одного пути, где-то лишнее ребро.