</>Экзамен без баговЕГЭ по информатике
Главная → Материалы → Задание 23

ЕГЭ по информатике · задание 23

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

Разбираем новое задание №23 ЕГЭ по информатике 2027: ориентированный взвешенный граф, кратчайший путь, алгоритм Дейкстры и готовое решение на Python.

199 просмотров
Проверить свой уровеньВсе материалы

Что изменилось в ЕГЭ по информатике 2027


В новой модели ЕГЭ тема прежнего задания №23 изменилась.

Теперь задание проверяет умение решать алгоритмические задачи, связанные с анализом графов. В частности, речь может идти о:

  • поиске оптимального пути между вершинами графа;
  • определении количества различных путей в ориентированном ациклическом графе.

В демонстрационном варианте дан именно первый тип: поиск кратчайшего пути.

Что дано в задании №23

В текстовом файле находится описание графа.

Каждая строка имеет вид:

L M W

где:

  • L — начальная вершина;
  • M — конечная вершина;
  • W — вес ребра между ними.

Например:

1 7 5.5

означает:

из вершины 1 можно перейти в вершину 7 по ребру весом 5,5.

Важно, что граф ориентированный.

Поэтому запись

1 7 5.5

означает переход:

1 → 7

но совсем не обязательно означает существование перехода:

7 → 1

Граф состоит из:

  • вершин;
  • рёбер — связей между вершинами.

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

Например:

1 ──5.5──→ 7

Число 5.5 — вес ребра.

Это может быть:

  • расстояние;
  • время;
  • стоимость;
  • расход топлива;
  • любой другой числовой параметр.

В задании №23 нас интересует сумма весов всех рёбер маршрута.

Задание №23 из демоверсии ЕГЭ 2027

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

Например, ребро из вершины 1 может находиться:

  • в начале файла;
  • в середине;
  • в конце.

Поэтому программа должна сначала прочитать весь граф, а затем искать путь.

Как представить граф в Python

Один из самых удобных вариантов — список смежности.

Создадим словарь:

PYTHONCODE
  1. graph = {}
Для каждой вершины будем хранить список переходов:
PYTHONCODE
  1. graph[1] = [(7, 5.5), (100, 12.0), (4, 2.5)]

Это означает:

из вершины 1 существуют рёбра:

1 → 7     вес 5.5
1 → 100   вес 12
1 → 4     вес 2.5

Алгоритм Дейкстры простыми словами

Представим, что мы начинаем в вершине 1.

До неё расстояние = 0


До всех остальных вершин сначала считаем расстояние бесконечным:

1 → 0

остальные → ∞

Теперь смотрим, куда можно попасть из 1.

Допустим:

1 → 7       5.5
1 → 4       2.5
1 → 100      12

Получаем:

до 7 = 5.5
до 4 = 2.5
до 100 = 12

Теперь выбираем вершину с наименьшим найденным расстоянием.

Это вершина:

4

потому что:

2.5 < 5.5 < 12

Из неё можно попасть в 100 с весом 8.

Получаем новый путь:

1 → 4 → 100

длиной:

2.5 + 8 = 10.5

Это лучше прежних 12, поэтому расстояние до 100 обновляем:

12 → 10.5

Следующая ближайшая вершина  7

Расстояние до неё = 5.5

Из неё ведёт ребро:

7 → 100

весом 2


Получаем:

5.5 + 2 = 7.5

Это ещё лучше:

10.5 → 7.5

Так постепенно алгоритм находит минимальное расстояние.

Решение нового задания №23 на Python

PYTHON
Считываем файл
  1. graph = {}
  3. with open("23.txt") as file:
  4. for line in file:
  5. L, M, W = line.split()
  7. L = int(L)
  8. M = int(M)
  9. W = float(W)
  11. if L not in graph:
  12. graph[L] = []
  14. graph[L].append((M, W))

Алгоритм Дейкстры

PYTHON
Алгоритм Дейкстры
  1. dist = {1: 0}
  2. used = set()
  4. while True:
  5. v = None
  7. for x in dist:
  8. if x not in used:
  9. if v is None or dist[x] < dist[v]:
  10. v = x
  12. if v is None:
  13. break
  15. if v == 100:
  16. break
  18. used.add(v)
  20. for to, w in graph.get(v, []):
  21. new_dist = dist[v] + w
  23. if to not in dist or new_dist < dist[to]:
  24. dist[to] = new_dist
  26. print(int(dist[100]))

Перебор путей рекурсией

PYTHON
Перебор путей рекурсией
  1. def way(x, total):
  2. if x == 100:
  3. ans.append(total)
  4. return
  6. if x not in graph:
  7. return
  9. for y, w in graph[x]:
  10. way(y, total + w)
  12. ans = []
  13. way(1, 0)
  15. print(int(min(ans)))

Что выбрать, рекурсию или алгоритм Дейкстры?

Если нужно просто понять идею задачи — начни с рекурсии.
Она наглядно показывает, как программа перебирает все возможные пути от стартовой вершины до конечной.

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

Если путей становится много — рекурсия может сильно замедлиться.
Она перебирает все возможные маршруты, даже если многие из них заранее невыгодны.

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

Для ЕГЭ важно понимать оба подхода.
Рекурсия помогает разобраться в логике графа, а Дейкстра — получить более универсальное и эффективное решение.

Если хочешь написать решение быстро на экзамене — выбирай то, что увереннее знаешь.
Ошибка в сложной реализации Дейкстры хуже, чем простая и правильно работающая рекурсия.

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

FAQ

Что появилось в задании №23 ЕГЭ по информатике 2027?

В новой версии задания №23 нужно решать алгоритмические задачи на графах. В демоверсии требуется найти кратчайший путь в ориентированном взвешенном графе.


Какой алгоритм нужен для задания №23?

Для демонстрационного задания удобно использовать алгоритм Дейкстры.


Можно ли решить задание без Дейкстры?

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


Почему используется float?

Потому что веса рёбер в файле могут быть вещественными, например 5.5.


Что выводить, если кратчайший путь равен 7.5?

Ответ 7 потому что в задании требуется целая часть длины.

Задание 1Теория по заданию №1 ЕГЭОткрыть разбор →Задание 1ЕГЭ №1. Объяснение решенияОткрыть разбор →Задание 2Логика ЕГЭ по информатике — таблицы истинности, операции и задание 2Открыть разбор →
Записаться на бесплатную диагностику