🚀 «Как решить задачу на графы в ЕГЭ за 10 минут: алгоритм Дейкстры на Python»

📌 «Графы пугают вас своей сложностью? На самом деле это просто точки и линии, которые могут принести 3-4 балла на ЕГЭ. Сегодня разберем, как решить задачу на поиск кратчайшего пути с помощью алгоритма Дейкстры — и всё это в Python!»

Что такое графы и зачем они нужны в ЕГЭ?

Граф — это структура из вершин (узлов) и рёбер (связей между ними). В ЕГЭ задачи на графы проверяют:

• Умение работать с взвешенными графами (где у рёбер есть «вес», например, расстояние).
• Понимание алгоритмов поиска: Дейкстры для кратчайшего пути, BFS/DFS для обхода.

🔍 Пример из жизни:
Представьте, что вершины — это города, а рёбра — дороги между ними с указанием длины. Ваша задача — найти самый короткий маршрут из Москвы в Сочи.

Разбор задачи из реального ЕГЭ

Условие:
«Найдите кратчайший путь от вершины A до вершины F во взвешенном графе. Веса рёбер указаны на рисунке (граф ниже). Ответ запишите в виде последовательности вершин и укажите длину пути».

Визуализация графа:

Copy

A --5--> B --3--> F
| ^ |
2 7 4
v | v
C --1--> D --2--> E

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

1. Создаем таблицу для хранения кратчайших расстояний до всех вершин. Изначально все расстояния, кроме стартовой вершины (A), равны бесконечности.
2. Выбираем вершину с минимальным расстоянием, которую ещё не обработали.
3. Обновляем расстояния до её соседей, если найден более короткий путь.
4. Повторяем, пока все вершины не будут обработаны.

Таблица после выполнения алгоритма:

ВершинаРасстояниеПредыдущая вершинаA0-B5AC2AD3 (C→D)CE5 (D→E)DF8 (B→F)B

Ответ: Кратчайший путь A → B → F, длина = 8.

Реализация алгоритма Дейкстры на Python

python

Copy

import heapq

def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)

if current_distance > distances[current_vertex]:
continue

for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances

# Описываем граф из задачи
graph = {
'A': {'B': 5, 'C': 2},
'B': {'F': 3},
'C': {'D': 1},
'D': {'B': 7, 'E': 2},
'E': {'F': 4},
'F': {}
}

print("Кратчайшие расстояния:", dijkstra(graph, 'A'))

Что выведет код:

Copy

Кратчайшие расстояния: {'A': 0, 'B': 5, 'C': 2, 'D': 3, 'E': 5, 'F': 8}

Лайфхак: Как визуализировать графы

Используйте библиотеку networkx и matplotlib, чтобы рисовать графы за пару строк:

python

Copy

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([
('A', 'B', {'weight': 5}),
('A', 'C', {'weight': 2}),
('B', 'F', {'weight': 3}),
('C', 'D', {'weight': 1}),
('D', 'B', {'weight': 7}),
('D', 'E', {'weight': 2}),
('E', 'F', {'weight': 4})
])

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue')
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()

Проверь себя!

✏️ Задание:
Дан граф:

Copy

X --2--> Y --4--> Z
| | ^
1 3 5
v v |
W --6--> T --1--> U

Найдите кратчайший путь от X до U. Напишите ответ в комментариях!

Почему это работает на ЕГЭ?

• Алгоритм Дейкстры решает задачи на графы за O(n log n), что экономит время.
• Понимание этого метода помогает решать не только ЕГЭ, но и олимпиадные задачи.

Хотите научиться решать такие задачи за 10 минут?
👉 Подписывайтесь на канал SvetIT — мы разбираем самые сложные темы ЕГЭ и ОГЭ простым языком.
👉 Первым 20 подписчикам — PDF-шпаргалка по алгоритмам в личные сообщения!

#ЕГЭ_графы #Python_алгоритмы #SvetIT

P.S. В следующей статье покажем, как адаптировать этот код для графов с тысячами вершин. Оставайтесь с нами! 💻🔍