Alterna · 24.2 — Кратчайшие пути (Дейкстра, A*, Беллман-Форд)

Навигаторы, протоколы маршрутизации (OSPF, BGP), игры (PathFinding) — все используют алгоритмы кратчайшего пути. MST (минимальный остов) — для сетей: минимум кабеля, чтобы все узлы были связаны.

ФГОСФОПЕГЭ №1олимпиадный

Алгоритм Дейкстры (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[B]	dist[C]	dist[D]	dist[E]	dist[F]
0	—	∞	∞	∞	∞	∞
1	A	7	3	∞	∞	∞
2	C	4	3	∞	8	∞
3	B	4	3	6	8	∞
4	D	4	3	6	8	12
5	E	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")

🐍Дейкстра: анимация кода

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* на сетке: интерактивный визуализатор

Старт

Цель

Открытый

Закрытый

Препятствие

Беллман-Форд (отрицательные веса)

В отличие от Дейкстры, алгоритм Беллмана-Форда работает с отрицательными весами и детектирует отрицательные циклы. Цена — бо́льшая сложность.

Алгоритм

Инициализация: 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-й итерации.

Когда использовать

Беллман-Форд нужен, когда в графе есть рёбра с отрицательными весами (например, финансовые модели с «доходами») или когда нужно проверить наличие отрицательных циклов. В остальных случаях предпочтительна Дейкстра.

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

Сравнение алгоритмов

Алгоритм	Сложность	Отриц. веса	Назначение	Особенности
Дейкстра	O((V+E)·log V)	Нет	Кратчайший путь из одной вершины	Жадный, неотрицательные веса
A*	O((V+E)·log V)*	Нет	PathFinding с эвристикой	Быстрее Дейкстры при хорошей h(v)
Беллман-Форд	O(V·E)	Да	Отрицательные веса, циклы	Детектирует отриц. циклы
Флойд-Уоршелл	O(V³)	Да	Все пары вершин	Матричная реализация
Минимальный остов (MST)
Прим	O((V+E)·log V)	—	MST	Лучше для плотных графов
Краскал	O(m·log m)	—	MST	Лучше для разреженных графов

* Сложность A* зависит от качества эвристики. В худшем случае — O((V+E)·log V) как у Дейкстры.

Выбор алгоритма

Все веса ≥ 0, нужен кратчайший путь → Дейкстра
Нужен путь + есть эвристика (сетка, карта) → A*
Есть отрицательные веса или циклы → Беллман-Форд
Нужны все пары кратчайших → Флойд-Уоршелл
Минимальный остов, плотный граф → Прим
Минимальный остов, разреженный граф → Краскал

Визуализатор Дейкстры

📍Дейкстра пошагово

MST Game — построй остов

Алгоритм Краскала: выбирай рёбра от самого лёгкого к самому тяжёлому. Если ребро соединяет разные компоненты — оно в MST. Если получается цикл — пропускаем.

🌲MST Game: найди минимальный остов

Выбери ребро с минимальным весом из доступных. Цель — собрать MST за 5 рёбер.

Вес MST: 0

Cut Property (теорема Краскала) В любом сечении графа минимальное по весу ребро, соединяющее две разные компоненты, принадлежит какому-то MST. Краскал эксплуатирует это: на каждом шаге добавляем самое лёгкое ребро, не создающее цикл.

Визуализатор Беллмана-Форда

На каждой из V−1 итераций все рёбра просматриваются и «релаксируются» — расстояния корректируются. На V-й итерации проверяется отрицательный цикл.

⚡Беллман-Форд пошагово

Отрицательный цикл Если на V-й итерации хотя бы одно расстояние уменьшилось — в графе есть достижимый отрицательный цикл. Кратчайшие пути не определены: можно уменьшать вес бесконечно.

🎯

Мини-тест: 5 вопросов

🧩Быстрый тест по теме

Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.

Шаг	u	dist[B]	dist[C]	dist[D]	dist[E]	dist[F]
0	—	∞	∞	∞	∞	∞
1	A	7	3	∞	∞	∞
2	C	4	3	∞	8	∞
3	B	4	3	6	8	∞
4	D	4	3	6	8	12
5	E	4	3	6	8	10

Шаг	u	dist[B]	dist[C]	dist[D]	dist[E]	dist[F]
0	—	∞	∞	∞	∞	∞
1	A	7	3	∞	∞	∞
2	C	4	3	∞	8	∞
3	B	4	3	6	8	∞
4	D	4	3	6	8	12
5	E	4	3	6	8	10

Шаг	u	dist[B]	dist[C]	dist[D]	dist[E]	dist[F]
0	—	∞	∞	∞	∞	∞
1	A	7	3	∞	∞	∞
2	C	4	3	∞	8	∞
3	B	4	3	6	8	∞
4	D	4	3	6	8	12
5	E	4	3	6	8	10