Кратчайшие пути: алгоритмы Дейкстры и Беллмана-Форда
Лекция
Кратчайшие пути: Dijkstra, Bellman–Ford (обзор)
Обновлено: ·~10 мин чтения
Лекция посвящена алгоритмам нахождения кратчайших путей в графах: Дейкстра и Беллмана-Форда. Рассматриваются их особенности и применение в условиях различных весов ребер.
кратчайшие пути
алгоритм Дейкстры
алгоритм Беллмана-Форда
взвешенные графы
поиск пути
отрицательные веса
навигация
оптимизация
Вопросы и ответы
Что такое алгоритм Дейкстры?
Алгоритм Дейкстры - жадный метод для нахождения кратчайших маршрутов от одного источника до всех остальных узлов в графе с неотрицательными весами.
Когда используется алгоритм Беллмана-Форда?
Алгоритм Беллмана-Форда используется для нахождения кратчайших путей в графах, где могут присутствовать отрицательные веса ребер.
Что такое отрицательный цикл?
Отрицательный цикл - это замкнутый путь в графе, сумма весов которого меньше нуля, что делает нахождение кратчайшего пути бессмысленным.
Почему алгоритм Дейкстры не подходит для отрицательных весов?
Алгоритм Дейкстры делает жадный выбор, основанный на текущих минимальных расстояниях, и не пересматривает их после фиксации, что приводит к ошибкам при отрицательных весах.
Фундаментальная концепция: Взвешенные графы и кратчайшие пути🔗
До этого мы работали с графами как с чистыми сетями связности, где алгоритм BFS (поиск в ширину) безошибочно находил кратчайший путь. Однако BFS эффективен лишь тогда, когда у всех ребер одинаковая стоимость. В реальности топология сети всегда дополнена метрикой: физическим расстоянием, временем в пути или финансовыми затратами на перелет.
Возьмем пример из жизни: если BFS помогает минимизировать количество пересадок в метро, то алгоритмы для взвешенных графов работают как современный навигатор. Система строит маршрут не по числу поворотов, а по суммарному времени движения с учетом пробок.
Допустим, задан ориентированный граф G=(V,E). Для каждого ребра (u,v)∈E определена весовая функция w(u,v)∈R, которая сопоставляет ребру числовое значение — его вес.
Путь p из вершины v0 в vk — это последовательность ⟨v0,v1,…,vk⟩. Весом или стоимостью пути w(p) считается сумма весов всех входящих в него ребер:
w(p)=∑i=1kw(vi−1,vi)
Кратчайшим путем между вершинами u и v считается вариант с минимальным суммарным весом:
δ(u,v)=min{w(p):upv}
В этой схеме поиск в ширину выбрал бы маршрут A→B, так как он состоит всего из одного ребра. Но в контексте взвешенного графа оптимальным будет путь A→C→B: его суммарный вес равен 2+1=3, что меньше прямого участка со стоимостью 5.
Когда у ребер появляются веса, обычная очередь FIFO перестает гарантировать нахождение лучшего маршрута. Требуются иные стратегии:
Алгоритм Дейкстры: задействует приоритетную очередь для жадного выбора ближайшей вершины.
Алгоритм Беллмана–Форда: применяет итеративную релаксацию ребер и умеет работать с отрицательными весами.
Теперь основная трудность заключается не в простом посещении узлов, а в эффективном обновлении оценок расстояний при обнаружении более выгодных цепочек ребер.
Алгоритм Дейкстры — классический жадный метод, вычисляющий кратчайшие маршруты от выбранного истока до всех остальных узлов графа. Логика его работы опирается на принцип оптимальности для подпутей: если наиболее короткий путь из точки A в точку C пролегает через узел B, то и отрезок A→B обязан быть кратчайшим для этой пары вершин.
Ключевым инструментом здесь выступает операция релаксации ребра (edge relaxation). Рассмотрим ситуацию: программа хранит текущую оценку расстояния до вершины v в переменной dist[v]. При проверке ребра (u,v) с весом w может выясниться, что маршрут до v через узел u выгоднее уже известного. В таком случае значение обновляется:
ifdist[u]+w<dist[v]:dist[v]=dist[u]+w
С математической точки зрения это постепенное снижение верхней границы (Upper Bound) предполагаемого расстояния до тех пор, пока она не достигнет своего минимума.
Для эффективной работы на каждом этапе необходимо выбирать ту вершину, до которой накоплено минимальное расстояние. Если использовать для этого простой список, поиск превратится в операцию O(V), что замедлит работу алгоритма до O(V2). Оптимизировать процесс помогает приоритетная очередь (Priority Queue) на базе бинарной кучи.
Такая структура данных позволяет извлекать минимальный элемент за O(logV), поэтому итоговая сложность сокращается до O((V+E)logV).
Алгоритм Дейкстры не рассчитан на работу с отрицательными весами ребер. Его жадная природа строится на постулате: добавление нового ребра к пути может только увеличить его общую длину или оставить её прежней. Если в структуре появится вес −5, узел, уже извлеченный из кучи как «финальный», может внезапно обнаружить более короткий путь через это ребро. Это разрушает логику корректной работы.
Для графов с отрицательными значениями применяется алгоритм Беллмана–Форда. Обратимся к нему в следующем блоке, затронув также тему «отрицательных циклов», которые делают поиск кратчайшего пути бессмысленным из-за бесконечного уменьшения суммы.
Алгоритм Беллмана–Форда: Борьба с отрицательными циклами🔗
Если метод Дейкстры напоминает направленный луч света, быстро прокладывающий маршрут в прозрачной среде, то алгоритм Беллмана–Форда приспособлен к работе в «искривленном» пространстве. Главное ограничение Дейкстры — невозможность корректно обрабатывать ребра с отрицательным весом. В таких условиях жадная стратегия дает сбой: зафиксировав узел как посещенный, алгоритм к нему больше не возвращается. Однако за рамками изученной области может существовать путь, который длиннее по количеству ребер, но выгоднее по итоговой «стоимости».
В основе подхода лежит принцип тотальной релаксации. Вместо использования очереди с приоритетом, мы V−1 раз (где V — число вершин) обходим все ребра графа, пытаясь улучшить текущие оценки кратчайших расстояний.
Число итераций V−1 выбрано не случайно: кратчайший путь в графе без циклов не может содержать больше ребер, чем количество вершин минус один. С каждым проходом алгоритм гарантированно фиксирует минимальную стоимость маршрутов, состоящих из i шагов. Рассмотрим это как распространение сигнала от источника: за каждый такт данные о минимальных затратах проникают на один уровень глубже в топологию сети.
def bellman_ford(vertices, edges, source):
# Инициализация: бесконечность для всех, кроме истока
distance = {v: float('inf') for v in vertices}
distance[source] = 0
# Основной цикл: V - 1 итераций
for _ in range(len(vertices) - 1):
for u, v, weight in edges:
# Релаксация: если найден путь короче - обновляем
if distance[u] != float('inf') and distance[u] + weight < distance[v]:
distance[v] = distance[u] + weight
# Проверка на наличие отрицательных циклов
for u, v, weight in edges:
if distance[u] != float('inf') and distance[u] + weight < distance[v]:
raise ValueError("Граф содержит отрицательный цикл")
return distance
Феномен отрицательного цикла возникает, когда сумма весов ребер в замкнутом контуре оказывается меньше нуля. В такой ситуации поиск кратчайшего пути теряет смысл: каждый новый круг будет бесконечно уменьшать итоговую стоимость, уводя ее к −∞.
В физических процессах обычные ребра поглощают энергию сигнала, а отрицательный цикл работает как усилитель, который при каждом проходе добавляет мощности фронту волны. Для корректно работающего графа после завершения вычислений должно соблюдаться условие:
∀(u,v)∈E:d[v]≤d[u]+w(u,v)
Если же на дополнительной, V-й итерации дистанция продолжает уменьшаться, это прямо указывает на аномалию — наличие замкнутой цепочки с отрицательным весом.
В сравнении с алгоритмом Дейкстры, который при использовании кучи показывает результат O(ElogV), метод Беллмана–Форда работает медленнее — за O(V⋅E). Для полносвязных структур это приводит к кубической сложности O(V3), что затрудняет его применение в масштабных сетях.
Тем не менее, способность обнаруживать аномалии делает его незаменимым в финансовом секторе (поиск арбитражных сделок на разнице курсов) или в классических протоколах маршрутизации (например, RIP).
Диаграмма загружается…
На схеме контур B-C-B имеет суммарный вес -8. Алгоритм зафиксирует бесконечное снижение стоимости на критической итерации.
Выбор между методами Дейкстры и Беллмана–Форда строится на балансе производительности и гибкости. Если структура графа исключает отрицательные веса, использование второго метода становится избыточным и неоправданно замедляет вычисления.
Характеристика
Алгоритм Дейкстры (с Priority Queue)
Алгоритм Беллмана–Форда
Временная сложность
O((V+E)logV)
O(V⋅E)
Сложность по памяти
O(V+E)
O(V)
Отрицательные ребра
Не допускаются
Допускаются
Отрицательные циклы
Не определяет
Обнаруживает
Тип графа
Любой
Ориентированный (для циклов)
При работе со списками смежности Дейкстра показывает преимущество на разреженных графах. В плотных структурах, где количество ребер E≈V2, разница сглаживается: сложность первого метода стремится к O(V2logV).
Корректность поиска пути зависит от обработки краевых случаев и особенностей типов данных. Кратко разберем основные риски.
Ловушка «Магического числа» (Бесконечность vs MAX_INT)
Инициализация массива dist значением 2147483647 (максимальный int32) часто приводит к сбоям. При попытке прибавить вес ребра к такому значению возникает переполнение (integer overflow), из-за чего дистанция превращается в огромное отрицательное число.
Решение: использовать константу, которая заведомо превышает возможную сумму всех весов, но оставляет запас для сложения, либо переходить на 64-битные типы.
Работа Дейкстры в среде с отрицательными весами
Опасно считать, что в таких условиях алгоритм просто вернет неточный результат. Если граф содержит отрицательный цикл, жадный выбор узла провоцирует бесконечную перерелаксацию, что ведет к зацикливанию. Даже без циклов наличие отрицательного веса нарушает инвариант оптимальности: алгоритм может зафиксировать вершину как посещенную до того, как найдет более выгодный маршрут через «минусовое» ребро.
Некорректная обработка недостижимых узлов
Во время релаксации важно проверять, достижима ли исходная вершина.
# Ошибка в Беллмане-Форде: релаксация "бесконечности"
for u, v, weight in edges:
if dist[u] != float('inf'): # Обязательная проверка
dist[v] = min(dist[v], dist[u] + weight)
Без этого условия алгоритм начнет «уменьшать» бесконечность на величину отрицательных весов. В итоге появятся фантомные маршруты к узлам, которые на самом деле изолированы.
Особенности неориентированных связей
Для Беллмана–Форда одно неориентированное ребро с отрицательным весом равносильно отрицательному циклу из двух вершин. Дейкстра в аналогичной ситуации попадет в петлю бесконечного обновления расстояний между этими точками.
Мы прошли путь от базового перебора связей в «плоских» структурах с помощью BFS до точечной навигации в нагруженных сетях. Теперь наш арсенал позволяет не просто находить достижимые узлы, но и минимизировать затраты ресурсов: времени, денег или топлива.
Эффективность методов Дейкстры и Беллмана–Форда ограничена контекстом задачи:
Статичность весов: Оба подхода предполагают, что веса ребер неизменны во время вычислений. Если стоимость пути меняется динамически, понадобятся иные инструменты.
Топологические ловушки: Отрицательные циклы делают поиск кратчайшего пути бессмысленным, так как итоговая стоимость стремится к −∞. Это требует предварительной проверки графа.
Локальность против глобальности: Изученные алгоритмы решают задачу SSSP (Single-Source Shortest Path). Для вычисления маршрутов между всеми парами узлов или внедрения эвристик используются более специализированные решения.
Диаграмма загружается…
Поиск кратчайшего маршрута — лишь частный случай оптимизации. В следующей лекции мы выйдем за рамки теории графов и изучим фундаментальные стратегии принятия решений. Мы выясним, в каких ситуациях «жадный» выбор мгновенной выгоды приводит к успеху, а когда для поиска истинного оптимума необходима мощь динамического программирования или перебора с возвратом (backtracking).
