Кратчайшие пути и MST

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 24 · страница 24.2
Кратчайшие пути и MST
Дейкстра, A*, Беллман-Форд. MST: Прим, Краскал. Сравнение алгоритмов.
Навигаторы, протоколы маршрутизации (OSPF, BGP), игры (PathFinding) — все используют алгоритмы кратчайшего пути. MST (минимальный остов) — для сетей: минимум кабеля, чтобы все узлы были связаны.
ФГОС
ФОП
ЕГЭ №1
олимпиадный
01
Алгоритм Дейкстры (single-source shortest path)
Алгоритм Дейкстры находит кратчайшие пути от одной стартовой вершины до всех остальных во
взвешенном графе с неотрицательными весами
.
Идея
Жадный алгоритм: поддерживаем текущее известное расстояние до каждой вершины. На каждом шаге выбираем необработанную вершину с
минимальным
расстоянием и «фиксируем» её — после этого расстояние до неё уже не уменьшится.
Инициализация: dist[start] = 0, dist[v] = ∞ для всех v ≠ start.
Создать
очередь с приоритетом
(min-heap), добавить все вершины с ключом dist[v].
Извлечь вершину
u
с минимальным dist — это текущая «ближайшая» непосещённая вершина.
Релаксация
: для каждого ребра u→v с весом w: если dist[u] + w < dist[v], обновить dist[v] = dist[u] + w.
Повторять шаги 3–4, пока очередь не пуста.
После завершения массив dist содержит кратчайшие расстояния от start до всех достижимых вершин.
Пример: 6 вершин
Граф: A→B(7), A→C(3), B→D(2), C→B(1), C→E(5), D→F(6), E→F(2), B→E(8). Старт = A.
Шаг
u
dist[A]
dist[B]
dist[C]
dist[D]
dist[E]
dist[F]
0
—
0
∞
∞
∞
∞
∞
1
A
0
7
3
∞
∞
∞
2
C
0
4
3
∞
8
∞
3
B
0
4
3
6
8
∞
4
D
0
4
3
6
8
12
5
E
0
4
3
6
8
10
Кратчайший путь A→C→B→E→F, расстояние = 10.
Сложность
С
бинарной кучей
: O((V + E) · log V). Каждая вершина извлекается из кучи один раз (V · log V), каждое ребро обрабатывается при релаксации (E · log V).
С
斐波那契 кучей
(теоретически): O(V · log V + E) — оптимальная, но сложная в реализации.
Ограничение
Алгоритм
не работает с отрицательными весами
. Причина: жадная фиксация расстояния. Если позже появится ребро с отрицательным весом, «зафиксированное» расстояние окажется неверным, и исправить его уже нельзя.
import heapq
def dijkstra(graph, start):
# graph[v] = [(u, w), ...] — список рёбер v→u с весом w
dist = {v: float('inf') for v in graph}
dist[start] = 0
pq = [(0, start)] # (расстояние, вершина)
while pq:
d, v = heapq.heappop(pq)
if d > dist[v]: continue # устаревший элемент
for u, w in graph[v]:
nd = d + w
if nd < dist[u]:
dist[u] = nd
heapq.heappush(pq, (nd, u))
return dist
# Пример:
graph = {
'A': [('B', 7), ('C', 3)],
'B': [('D', 2), ('E', 8)],
'C': [('B', 1), ('E', 5)],
'D': [('F', 6)],
'E': [('F', 2)],
'F': []
}
dist = dijkstra(graph, 'A')
print(f"A→F = {dist['F']}") # 10
print(f"Путь: A → C → B → E → F")
🐍
Дейкстра: анимация кода
02
A* — Дейкстра + эвристика
A* минимизирует
f(v) = g(v) + h(v)
, где:
g(v)
— реальная стоимость пути от старта до v (как у Дейкстры).
h(v)
— эвристика: оценка стоимости от v до цели.
Когда h ≡ 0, A* превращается в обычную Дейкстру. Эвристика направляет поиск к цели, уменьшая число обработанных вершин.
Эвристики для сетки
Эвристика
Формула
Движение
Манхэттен
|x₁ − x₂| + |y₁ − y₂|
4-направленная сетка
Евклидова
√((x₁ − x₂)² + (y₁ − y₂)²)
Любое направление
Чебышёва
max(|x₁ − x₂|, |y₁ − y₂|)
8-направленная сетка
Допустимость эвристики
Эвристика
допустима
(admissible), если h(v) ≤ h*(v) для всех v, где h*(v) — истинная стоимость до цели. Если эвристика допустима и
монотонна
(гёлдерова: h(a) ≤ cost(a,b) + h(b)), A* гарантирует оптимальный путь.
Сравнение с Дейкстрой
A* быстрее Дейкстры на практике, если хорошая эвристика. В худшем случае (h ≡ 0 или плохая эвристика) — такая же сложность, как у Дейкстры: O((V+E)·log V).
import heapq
def astar(graph, start, goal, h):
# h(v) — эвристика: оценка расстояния от v до goal
open_set = [(h(start), 0, start)] # (f, g, v)
g_score = {start: 0}
came_from = {}
while open_set:
f, g, v = heapq.heappop(open_set)
if v == goal:
# восстановление пути
path = []
while v in came_from:
path.append(v)
v = came_from[v]
path.append(start)
return path[::-1], g_score[goal]
if g > g_score.get(v, float('inf')):
continue
for u, w in graph.get(v, []):
ng = g + w
if ng < g_score.get(u, float('inf')):
came_from[u] = v
g_score[u] = ng
nf = ng + h(u)
heapq.heappush(open_set, (nf, ng, u))
return None, float('inf') # путь не найден
# Пример сетки 4×4, Манхэттенская эвристика:
def manhattan(a, b, cols=4):
return abs(a // cols - b // cols) + abs(a % cols - b % cols)
grid = {(i, j): [] for i in range(4) for j in range(4)}
# ... строим граф из соседних клеток ...
# path, cost = astar(grid, start=0, goal=15, h=lambda v: manhattan(v, 15))
🧭
A* на сетке: интерактивный визуализатор
Старт
Цель
Открытый
Закрытый
Препятствие
03
Беллман-Форд (отрицательные веса)
В отличие от Дейкстры, алгоритм Беллмана-Форда работает с
отрицательными весами
и
детектирует отрицательные циклы
. Цена — бо́льшая сложность.
Алгоритм
Инициализация: dist[start] = 0, dist[v] = ∞ для всех v ≠ start.
Повторить
V − 1 раз
: для каждого ребра (u, v, w) выполнить релаксацию: если dist[u] + w < dist[v], обновить dist[v] = dist[u] + w.
Проверка на отрицательный цикл
: пройтись по всем рёбрам ещё раз. Если хотя бы одно расстояние уменьшилось — в графе есть отрицательный цикл, достижимый из старта.
Почему именно V − 1 итераций?
Кратчайший путь без циклов содержит
не более V − 1 рёбер
. За каждую итерацию алгоритм «обнаруживает» кратчайшие пути длины до k рёбер (k — номер итерации). За V − 1 итераций гарантированно находятся все такие пути.
Сложность
O(V · E)
— на каждой из V − 1 итераций обходим все E рёбер. Медленнее Дейкстры, но зато поддерживает отрицательные веса.
Отрицательный цикл
Граф: A→B(1), B→C(−3), C→B(1). Путь B→C→B: суммарный вес −3 + 1 = −2. Цикл с отрицательным весом — расстояние можно уменьшать бесконечно. Алгоритм обнаружит это на V-й итерации.
Когда использовать
Беллман-Форд нужен, когда в графе есть рёбра с отрицательными весами (например, финансовые модели с «доходами») или когда нужно проверить наличие отрицательных циклов. В остальных случаях предпочтительна Дейкстра.
04
MST: Прим и Краскал
MST (Minimum Spanning Tree)
— подграф, соединяющий все вершины с
минимальной суммой весов
и без циклов. В MST ровно V − 1 ребро.
Теорема Крускала
Все MST одного графа имеют одинаковую суммарную стоимость. Если все веса различны — MST единственна.
Алгоритм Прима
Начать с любой вершины.
Из всех рёбер, соединяющих посещённые и непосещённые вершины, выбрать
минимальное
.
Добавить ребро и новую вершину.
Повторять, пока не посещены все V вершин.
Сложность:
O((V+E)·log V) с кучей (при плотном графе — O(V²)).
Лучше для
плотных
графов.
Алгоритм Краскала
Отсортировать все рёбра по весу.
Брать рёбра по порядку (от меньшего к большему).
Добавлять, если ребро
не образует цикл
(проверка через DSU — структура «непересекающихся множеств»).
Повторять, пока не добавлено V − 1 ребро.
Сложность:
O(m · log m), где m = |E|.
Лучше для
разреженных
графов.
🌲
Прим: пошаговое построение MST
05
Сравнение алгоритмов
Алгоритм
Сложность
Отриц. веса
Назначение
Особенности
Дейкстра
O((V+E)·log V)
Нет
Кратчайший