ТурбоУроки
На главнуюВсе задания
ЕГЭ по информатике›Задание 23
ЕГЭ 2026 · Задание 23

Анализ графов

Чтение взвешенного ориентированного графа из файла и кратчайший путь в DAG.

Повышенный уровеньГрафыPython45–55 мин✓ Полный урок
01

Что нужно понимать

Чтение взвешенного ориентированного графа из файла и кратчайший путь в DAG.

→

Ориентированное ребро

Запись L M W означает переход только из L в M с весом W.

DAG

Без циклов

Для ациклического графа кратчайшие пути удобно считать динамикой по топологическому порядку.

dist

Расстояние

dist[v] — минимальная известная сумма весов пути из старта в v.

Ключевая идея

Не считайте граф неориентированным: строка L M W задаёт направление L → M. Для нового формата задания №23 нужно уметь читать файл и программно искать кратчайший путь.

02

Надёжный алгоритм решения

1

Считай рёбра

Для каждой строки сохрани L, M и вещественный вес W.

2

Построй список смежности

Из каждой вершины храни исходящие рёбра.

3

Задай dist[start]=0

Остальные расстояния сначала равны бесконечности.

4

Расслабляй рёбра

Для DAG — в топологическом порядке; универсально можно применить Дейкстру при положительных весах.

5

Возьми целую часть

Если это прямо требует условие, применяй int к итоговой длине, а не к каждому ребру.

Типичная ошибка: Не отбрасывайте дробную часть каждого веса отдельно. Сначала найдите точную сумму пути, только затем берите целую часть итогового значения.
03

Пошаговый разбор

Рёбра: 1→2 (2.5), 1→3 (4), 2→4 (3), 3→4 (1), 2→5 (7), 4→5 (2). Найдём путь 1→5.

Исходные данныеМодель
1 2 2.5
1 3 4.0
2 4 3.0
3 4 1.0
2 5 7.0
4 5 2.0
РезультатРазбор

Через 2 и 4: 2.5+3+2 = 7.5.

Через 3 и 4: 4+1+2 = 7.0.

Кратчайшая длина — 7.0, целая часть — 7.

РазборОткрывай шаги по очереди

min(2.5+3, 4+1)=min(5.5,5)=5.

min(2.5+7, 5+2)=min(9.5,7)=7.

Целая часть 7.0 равна 7.

04

Тренажёр

Ответь на оба вопроса. Правильные ответы автоматически отмечают практику выполненной.

Практика

Закрепи алгоритм

2 вопроса

Какова кратчайшая длина пути из 1 в 4 в примере?

Какова целая часть кратчайшего пути из 1 в 5?

05

Шпаргалка на экзамен

  1. L M W означает ориентированное ребро L→M.
  2. Храни dist[v] — минимальную длину пути.
  3. При положительных весах подходит Дейкстра; для DAG — топологическая динамика.
  4. Округление/целую часть применяй только в самом конце.
Урок 23 завершён

Продолжай по маршруту

Прогресс урока сохраняется локально в браузере.

← Задание 22Задание 24 →

Тематика «Анализ графов» сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗