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

Администратор

6 дней назад

ЕГЭ информатика 23 задание разбор, теория, как решать.

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

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

В спецификации задания указаны следующие основные направления:

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

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

1. Что такое граф

Граф — это структура, состоящая из вершин и рёбер.

Например:

1 → 2 → 5
↓
3 → 4

1 → 2 → 5

↓

3 → 4

Здесь числа 1, 2, 3, 4 и 5 — это вершины графа,
а стрелки между ними — рёбра.

Основные понятия

Понятие	Описание
Вершина	Отдельный объект графа
Ребро	Связь между двумя вершинами
Путь	Последовательность рёбер, по которым можно перейти из одной вершины в другую
Вес ребра	Числовое значение, соответствующее ребру
Длина пути	Сумма весов всех рёбер, входящих в путь

2. Ориентированный граф

В ориентированном графе каждое ребро имеет направление.

Например:

1 → 2

1 → 2

означает, что можно перейти из вершины 1 в вершину 2.
Это не означает, что можно автоматически перейти обратно:

2 → 1

2 → 1

Такое ребро должно быть задано отдельно.

3. Неориентированный граф

В неориентированном графе ребро не имеет направления.

1 — 2

1 — 2

Это означает, что можно перейти как из 1 в 2, так и из 2 в 1.

4. Взвешенный граф

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

Например:

1 → 7   вес 5.5
7 → 100 вес 2.0

1 2	1 → 7 вес 5.5 7 → 100 вес 2.0

Длина пути

1 → 7 → 100

1	1 → 7 → 100

равна:

5.5 + 2.0 = 7.5

1	5.5 + 2.0 = 7.5

5. Ациклический граф

Ациклический граф — это граф, в котором невозможно,
двигаясь по рёбрам, вернуться в исходную вершину.

Например:

1 → 2 → 3 → 4

1	1 → 2 → 3 → 4

Цикла здесь нет.

А в графе

1 → 2 → 3
↑       ↓
└───────┘

1 → 2 → 3

↑ ↓

└───────┘

есть цикл:

1 → 2 → 3 → 1

1	1 → 2 → 3 → 1

Поэтому такой граф не является ациклическим.

Ориентированный ациклический граф часто обозначают сокращением
DAG — Directed Acyclic Graph.

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

В задании граф обычно задаётся в текстовом файле.
Каждая строка может содержать:

L M W

L M W

где:

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

Например:

1 7 5.5

7 100 2.0

1 100 12.0

1 4 2.5

4 100 8.0

Эти строки описывают рёбра:

1 → 7     вес 5.5
7 → 100   вес 2.0
1 → 100   вес 12.0
1 → 4     вес 2.5
4 → 100   вес 8.0

1 → 7 вес 5.5

7 → 100 вес 2.0

1 → 100 вес 12.0

1 → 4 вес 2.5

4 → 100 вес 8.0

7. Как хранить граф в Python

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

g = [[] for i in range(1001)]

1	g = [[] for i in range(1001)]

Для каждой вершины создаётся отдельный список рёбер.

Читаем файл:

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b, w = line.split()

    a = int(a)
    b = int(b)
    w = float(w)

    g[a].append((b, w))

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

g[a].append((b, w))

Например, если есть строки:

1 7 5.5
1 4 2.5
1 100 12.0

1 7 5.5

1 4 2.5

1 100 12.0

то:

g[1]

g[1]

будет содержать:

[(7, 5.5), (4, 2.5), (100, 12.0)]

1	[(7, 5.5), (4, 2.5), (100, 12.0)]

8. Основные типы задания 23

По формулировке спецификации можно выделить два главных направления:

Тип задачи	Основной метод
Поиск оптимального или кратчайшего пути	Алгоритм Дейкстры или динамика на DAG
Количество различных путей	Рекурсия с мемоизацией или динамическое программирование

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

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

Типичная формулировка:

Найдите длину кратчайшего пути из вершины 1 в вершину 100.

Основная идея алгоритма

Для каждой вершины храним минимальное найденное расстояние от стартовой вершины.

Например:

d[1] = 0

d[1] = 0

означает, что расстояние от вершины 1 до самой себя равно 0.

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

d = [float('inf')] * 1001
d[1] = 0

1 2	d = [float('inf')] * 1001 d[1] = 0

Очередь с приоритетом

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

from heapq import *

1	from heapq import *

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

Создаём очередь:

q = [(0, 1)]

1	q = [(0, 1)]

Пара означает:

(расстояние, вершина)

1	(расстояние, вершина)

Полный шаблон алгоритма Дейкстры

from heapq import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b, w = line.split()
    a = int(a)
    b = int(b)
    w = float(w)

    g[a].append((b, w))

d = [float('inf')] * 1001
d[1] = 0

q = [(0, 1)]

while q:
    dist, v = heappop(q)

    if dist != d[v]:
        continue

    for to, w in g[v]:
        nd = dist + w

        if nd < d[to]:
            d[to] = nd
            heappush(q, (nd, to))

print(int(d[100]))

from heapq import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

g[a].append((b, w))

d = [float('inf')] * 1001

d[1] = 0

q = [(0, 1)]

while q:

dist, v = heappop(q)

if dist != d[v]:

continue

for to, w in g[v]:

nd = dist + w

if nd < d[to]:

d[to] = nd

heappush(q, (nd, to))

print(int(d[100]))

10. Как работает алгоритм Дейкстры

Рассмотрим пример:

1 → 100   12.0
1 → 4      2.5
4 → 100    8.0
1 → 7      5.5
7 → 100    2.0

1 → 100 12.0

1 → 4 2.5

4 → 100 8.0

1 → 7 5.5

7 → 100 2.0

Сначала можно попасть напрямую:

1 → 100 = 12

1	1 → 100 = 12

Затем находится путь:

1 → 4 → 100

1	1 → 4 → 100

Его длина:

2.5 + 8 = 10.5

1	2.5 + 8 = 10.5

Он короче 12, поэтому значение обновляется:

d[100] = 10.5

1	d[100] = 10.5

Затем находится путь:

1 → 7 → 100

1	1 → 7 → 100

Его длина:

5.5 + 2 = 7.5

1	5.5 + 2 = 7.5

Теперь:

d[100] = 7.5

1	d[100] = 7.5

Это и есть кратчайший путь.

11. Что делает условие nd < d[to]

Одна из самых важных строк алгоритма:

if nd < d[to]:

1	if nd < d[to]:

Здесь:

nd — новое расстояние;
d[to] — лучшее расстояние, найденное раньше.

Если новый путь короче старого, значение заменяется:

d[to] = nd

1	d[to] = nd

12. Зачем нужен heapq

Функция:

heappush(q, (nd, to))

1	heappush(q, (nd, to))

добавляет новый элемент в очередь.

Функция:

heappop(q)

1	heappop(q)

извлекает элемент с минимальным первым значением.

То есть если в очереди:

(12, 100)
(2.5, 4)
(5.5, 7)

(12, 100)

(2.5, 4)

(5.5, 7)

первой будет извлечена вершина 4, потому что расстояние 2.5 минимально.

13. Почему используется float(‘inf’)

Запись:

float('inf')

1	float('inf')

означает бесконечно большое число.

Поэтому в начале можно записать:

d = [float('inf')] * 1001

1	d = [float('inf')] * 1001

Это означает, что пока расстояние до всех вершин неизвестно.

Для начальной вершины:

d[1] = 0

d[1] = 0

14. Когда используется int()

Если в условии сказано:

Запишите целую часть длины кратчайшего пути.

необходимо использовать:

int(d[100])

1	int(d[100])

Например:

int(7.5)

int(7.5)

даёт:

7

Это не округление, а отбрасывание дробной части.

15. Количество различных путей

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

Например:

Сколько существует различных путей из вершины 1 в вершину 100?

Здесь алгоритм Дейкстры не нужен, потому что нас интересует не длина пути,
а количество возможных маршрутов.

16. Простой пример подсчёта путей

Пусть граф имеет вид:

1 → 2 → 100
↓
3 → 100

1 → 2 → 100

↓

3 → 100

Существует два пути:

1 → 2 → 100

1 → 3 → 100

1 → 2 → 100

1 → 3 → 100

Следовательно, ответ равен 2.

17. Подсчёт путей с помощью рекурсии

Для ациклического графа удобно использовать рекурсивную функцию.

def f(v):
    if v == 100:
        return 1

    s = 0

    for to in g[v]:
        s += f(to)

    return s

def f(v):

if v == 100:

return 1

s = 0

for to in g[v]:

s += f(to)

return s

Логика очень простая:

Если мы дошли до конечной вершины 100, значит найден один путь:

if v == 100:
    return 1

1 2	if v == 100: return 1

Для каждой следующей вершины подсчитываем количество путей:

for to in g[v]:
    s += f(to)

1 2	for to in g[v]: s += f(to)

18. Зачем нужна мемоизация

Одна и та же вершина может встречаться в нескольких путях.
Чтобы не вычислять результат для неё много раз,
можно использовать:

from functools import lru_cache

1	from functools import lru_cache

и декоратор:

@lru_cache(None)

1	@lru_cache(None)

Полный вариант:

from functools import *

@lru_cache(None)
def f(v):
    if v == 100:
        return 1

    s = 0

    for to in g[v]:
        s += f(to)

    return s

print(f(1))

from functools import *

@lru_cache(None)

def f(v):

if v == 100:

return 1

s = 0

for to in g[v]:

s += f(to)

return s

print(f(1))

19. Если граф хранит веса рёбер

Если в списке смежности хранятся пары:

(вершина, вес)

1	(вершина, вес)

то цикл будет выглядеть так:

for to, w in g[v]:
    s += f(to)

1 2	for to, w in g[v]: s += f(to)

Вес здесь не используется, потому что мы считаем только количество путей.

20. Кратчайший путь в ациклическом графе с помощью рекурсии

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

from functools import *

@lru_cache(None)
def f(v):
    if v == 100:
        return 0

    ans = float('inf')

    for to, w in g[v]:
        x = f(to)

        if x != float('inf'):
            ans = min(ans, w + x)

    return ans

print(int(f(1)))

from functools import *

@lru_cache(None)

def f(v):

if v == 100:

return 0

ans = float('inf')

for to, w in g[v]:

x = f(to)

if x != float('inf'):

ans = min(ans, w + x)

return ans

print(int(f(1)))

Функция:

f(v)

f(v)

возвращает минимальное расстояние от вершины v
до вершины 100.

Для конечной вершины:

f(100) = 0

1	f(100) = 0

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

ans = min(ans, w + x)

1	ans = min(ans, w + x)

21. Максимальный путь в DAG

В ориентированном ациклическом графе можно аналогичным способом искать
и самый длинный путь.

Главное отличие — вместо min() используется max().

from functools import *

@lru_cache(None)
def f(v):
    if v == 100:
        return 0

    ans = -float('inf')

    for to, w in g[v]:
        x = f(to)

        if x != -float('inf'):
            ans = max(ans, w + x)

    return ans

print(f(1))

from functools import *

@lru_cache(None)

def f(v):

if v == 100:

return 0

ans = -float('inf')

for to, w in g[v]:

x = f(to)

if x != -float('inf'):

ans = max(ans, w + x)

return ans

print(f(1))

22. Динамическое программирование на графе

Мемоизация с помощью lru_cache — это один из вариантов
динамического программирования.

Идея заключается в том, что результат для каждой вершины вычисляется один раз,
а затем сохраняется.

Например:

f(7)

f(7)

может означать:

количество путей из 7 в 100;
минимальную длину пути из 7 в 100;
максимальную длину пути из 7 в 100.

Смысл функции зависит от конкретного условия задачи.

23. Как выбрать нужный алгоритм

Формулировка задачи	Подход
Найдите длину кратчайшего пути	Алгоритм Дейкстры
Найдите минимальную сумму весов	Алгоритм Дейкстры
Найдите минимальную стоимость маршрута	Алгоритм Дейкстры
Определите количество различных путей	Рекурсия + мемоизация
Найдите кратчайший путь в DAG	Дейкстра или динамика
Найдите максимальную длину пути в DAG	Динамическое программирование

24. Шаблон 1 — кратчайший путь

from heapq import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b, w = line.split()
    a = int(a)
    b = int(b)
    w = float(w)

    g[a].append((b, w))

d = [float('inf')] * 1001
d[1] = 0

q = [(0, 1)]

while q:
    dist, v = heappop(q)

    if dist != d[v]:
        continue

    for to, w in g[v]:
        nd = dist + w

        if nd < d[to]:
            d[to] = nd
            heappush(q, (nd, to))

print(int(d[100]))

from heapq import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

g[a].append((b, w))

d = [float('inf')] * 1001

d[1] = 0

q = [(0, 1)]

while q:

dist, v = heappop(q)

if dist != d[v]:

continue

for to, w in g[v]:

nd = dist + w

if nd < d[to]:

d[to] = nd

heappush(q, (nd, to))

print(int(d[100]))

25. Шаблон 2 — количество различных путей

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b = map(int, line.split())
    g[a].append(b)

@lru_cache(None)
def F(v):
    if v == 100:
        return 1

    s = 0

    for to in g[v]:
        s += F(to)

    return s

print(F(1))

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b = map(int, line.split())

g[a].append(b)

@lru_cache(None)

def F(v):

if v == 100:

return 1

s = 0

for to in g[v]:

s += F(to)

return s

print(F(1))

26. Шаблон 3 — количество путей, если в файле есть вес

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b, w = line.split()
    a = int(a)
    b = int(b)
    w = float(w)

    g[a].append((b, w))

@lru_cache(None)
def F(v):
    if v == 100:
        return 1

    s = 0

    for to, w in g[v]:
        s += F(to)

    return s

print(F(1))

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

g[a].append((b, w))

@lru_cache(None)

def F(v):

if v == 100:

return 1

s = 0

for to, w in g[v]:

s += F(to)

return s

print(F(1))

27. Шаблон 4 — минимальный путь в DAG

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:
    a, b, w = line.split()
    a = int(a)
    b = int(b)
    w = float(w)

    g[a].append((b, w))

@lru_cache(None)
def F(v):
    if v == 100:
        return 0

    ans = float('inf')

    for to, w in g[v]:
        x = F(to)

        if x != float('inf'):
            ans = min(ans, w + x)

    return ans

print(int(F(1)))

from functools import *

f = open('23.txt')

g = [[] for i in range(1001)]

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

g[a].append((b, w))

@lru_cache(None)

def F(v):

if v == 100:

return 0

ans = float('inf')

for to, w in g[v]:

x = F(to)

if x != float('inf'):

ans = min(ans, w + x)

return ans

print(int(F(1)))

28. Что необходимо знать для задания 23

Для решения задания 23 рекомендуется уверенно понимать следующие темы:

что такое вершина и ребро графа;
ориентированный и неориентированный граф;
взвешенный граф;
ациклический граф;
путь и длина пути;
чтение графа из файла;
список смежности;
алгоритм Дейкстры;
работу heapq;
рекурсию;
мемоизацию с помощью lru_cache;
динамическое программирование на ориентированном ациклическом графе;
подсчёт количества различных путей.

29. Главное для ЕГЭ

Перед написанием программы необходимо определить, что именно требуется найти.

Если в условии встречаются слова:

кратчайший путь
минимальная сумма весов
минимальная стоимость

кратчайший путь

минимальная сумма весов

минимальная стоимость

в первую очередь следует подумать об алгоритме Дейкстры.

Если требуется:

количество различных путей

1	количество различных путей

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

Таким образом, для задания 23 особенно важно не просто запомнить один код,
а научиться определять тип задачи и выбирать подходящий алгоритм.