PricingLoginStart free
DSA Interview Prep · Урок

Беллман—Форд и отрицательные циклы

Выполните n-1 проходов релаксации по всем рёбрам, обнаружьте отрицательные циклы дополнительным проходом и объясните, почему Дейкстра не работает с рёбрами отрицательного веса

Урок 2 из 413 шагов

«Беллман—Форд и отрицательные циклы» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Зачем нужен алгоритм Беллмана—Форда

Алгоритм Беллмана—Форда, как и алгоритм Дейкстры, решает задачу поиска кратчайших путей из одного источника, но умеет работать с отрицательными весами рёбер. Он также обнаруживает отрицательные циклы — циклы, суммарный вес которых отрицателен, из-за чего невозможно определить конечный кратчайший путь через них. Хотя алгоритм Беллмана—Форда медленнее алгоритма Дейкстры, он является правильным выбором, если граф может содержать рёбра с отрицательными весами.

Релаксация: основная операция

Алгоритм Беллмана—Форда строится на одной операции: релаксации. Релаксация ребра (u, v, w) означает следующее: если dist[u] + w < dist[v], обновите dist[v] = dist[u] + w. Мы многократно релаксируем все рёбра. Главная идея такова: любой кратчайший путь содержит не более V-1 рёбер (в графе без отрицательных циклов). Поэтому V-1 проходов по всем рёбрам с релаксацией достаточно, чтобы найти все кратчайшие пути.

Реализация алгоритма Беллмана—Форда

Представьте граф в виде списка рёбер [(u, v, weight)]. Инициализируйте dist[source] = 0, а все остальные значения установите равными inf. Выполните V-1 проходов, релаксируя все рёбра на каждом проходе. Любое обновление, которое происходит на V-м проходе, указывает на наличие отрицательного цикла.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

Почему достаточно V-1 проходов

Кратчайший путь в графе без отрицательных циклов проходит через каждую вершину не более одного раза, поэтому содержит не более V-1 рёбер. После первого прохода оптимальными становятся кратчайшие пути с одним переходом. После второго прохода — кратчайшие пути с двумя переходами. После V-1 проходов найдены все кратчайшие пути, использующие не более V-1 переходов. Если на проходе V расстояние всё ещё обновляется, граф содержит отрицательный цикл, достижимый из источника.

Обнаружение отрицательных циклов

После V-1 проходов выполните ещё один проход по всем рёбрам. Если для какого-либо ребра (u, v, w) выполняется условие dist[u] + w < dist[v], значит, существует отрицательный цикл, а кратчайшее расстояние до некоторых вершин равно -infinity. Практические применения включают обнаружение возможностей арбитража при обмене валютами (отрицательные циклы в графах с log-весами) и обнаружение противоречий в системах ограничений.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

Сравнение алгоритмов Дейкстры и Беллмана—Форда

Алгоритм Дейкстры: O((V+E) log V), требует неотрицательных весов, использует жадный подход. Алгоритм Беллмана—Форда: O(V × E), работает с отрицательными весами и обнаруживает отрицательные циклы. Для большинства задач на собеседованиях с неотрицательными весами предпочтителен алгоритм Дейкстры. Если появляются отрицательные веса, например в задачах «найти кратчайший путь по рёбрам с отрицательной стоимостью» или «обнаружить арбитраж», ответом будет алгоритм Беллмана—Форда. Для плотных графов наихудший случай O(V³) у алгоритма Беллмана—Форда сопоставим с алгоритмом Флойда—Уоршелла.

Применение: самые дешёвые перелёты с алгоритмом Беллмана—Форда

Задачу о самых дешёвых перелётах с максимумом K пересадок (LeetCode 787) можно решить с помощью модифицированного алгоритма Беллмана—Форда: выполните ровно k+1 проходов релаксации, поскольку k пересадок означают k+1 рёбер. Используйте копию расстояний, полученных на предыдущем проходе, чтобы за один проход не использовать больше разрешённого числа переходов: иначе один проход мог бы объединить несколько переходов в цепочку.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA: оптимизация на основе очереди

Алгоритм ускоренного поиска кратчайших путей (SPFA) — это оптимизированный алгоритм Беллмана—Форда, который повторно релаксирует только рёбра вершин, расстояние до которых было только что обновлено, используя очередь. Средняя сложность составляет O(E), но в наихудшем случае она по-прежнему равна O(V × E). SPFA редко требуется на собеседованиях, но его можно упомянуть как оптимизацию, если алгоритм Беллмана—Форда работает слишком медленно на разреженных графах. В Python нет встроенной реализации SPFA, но её несложно реализовать с помощью collections.deque.

Обнаружение валютного арбитража

Классическое применение алгоритма Беллмана—Форда: по заданным курсам обмена валют определить, возможен ли арбитраж — цикл, в котором после конвертации валют вы получаете больше, чем было изначально. Преобразуйте веса, взяв отрицательные логарифмы обменных курсов. Арбитраж = цикл с отрицательной суммой log-весов = отрицательный цикл, обнаруживаемый алгоритмом Беллмана—Форда. Так реальные финансовые задачи сводятся к стандартному алгоритму.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

Оптимизация с досрочным завершением

Если за полный проход по всем рёбрам не обновилось ни одного расстояния, последующие проходы также ничего не изменят — завершите работу досрочно. Эта оптимизация уменьшает сложность в лучшем случае до O(E), когда граф уже становится оптимальным после небольшого числа проходов. В начале каждого прохода добавляйте флаг updated = False; если после прохода он остаётся ложным, немедленно прерывайте цикл.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

Алгоритм Беллмана—Форда на графах со списками смежности

Если граф задан списком смежности, а не списком рёбер, сначала преобразуйте его в список рёбер либо переберите все записи списка смежности как рёбра. При V=1000 и E=5000 выполнение V-1=999 проходов, каждый из которых просматривает 5000 рёбер, даёт 4,995,000 операций — это укладывается в ограничения по времени. Для очень плотных графов (E ≈ V²) наихудший случай O(V³) совпадает с алгоритмом Флойда—Уоршелла, поэтому выбор зависит от контекста.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Быстрая проверка

Проверьте своё понимание концепций структур данных и алгоритмов — подготовки к собеседованию по программированию, рассмотренных в этом уроке.

Ответь в интерактивном уроке

Итоги урока

В этом уроке вы узнали: алгоритм Беллмана—Форда релаксирует все рёбра V-1 раз, чтобы обрабатывать рёбра с отрицательными весами, V-й проход релаксации, на котором всё ещё находятся улучшения, указывает на отрицательный цикл, а сложность алгоритма составляет O(V × E) по сравнению с O((V+E) log V) у алгоритма Дейкстры. Далее мы рассмотрим алгоритм Флойда—Уоршелла для поиска кратчайших путей между всеми парами вершин за одно вычисление сложности O(V³).

Можно начать бесплатно

Изучай Python с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы
30
Уроки
120
Начать учиться бесплатноПосмотреть полный курс

Часто задаваемые вопросы

Урок «Беллман—Форд и отрицательные циклы» бесплатный?

Да — полный текст урока «Беллман—Форд и отрицательные циклы» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Беллман—Форд и отрицательные циклы»?

Выполните n-1 проходов релаксации по всем рёбрам, обнаружьте отрицательные циклы дополнительным проходом и объясните, почему Дейкстра не работает с рёбрами отрицательного веса Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Беллман—Форд и отрицательные циклы»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Алгоритм Дейкстры с очередью с приоритетами
  2. Беллман—Форд и отрицательные циклы
  3. Флойд—Уоршелл: кратчайшие пути между всеми парами
  4. Задержка в сети и восстановление пути
← Назад к DSA Interview Prep