0Pricing
Coding Interview Prep · Урок

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

Обрабатывайте отрицательные рёбра и находите циклы

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

Когда алгоритм Дейкстры не работает

Алгоритм Дейкстры считает извлечённое расстояние окончательным, но отрицательное ребро позже может сделать путь дешевле. Поэтому алгоритм не работает.

Знакомьтесь: Беллман — Форд

Алгоритм Беллмана — Форда работает с отрицательными весами рёбер. Он медленнее алгоритма Дейкстры, но надёжен там, где жадной логике доверять нельзя.

Основная операция

Алгоритм многократно выполняет релаксацию каждого ребра: если dist[u] плюс вес ребра меньше dist[v], обновите dist[v] этим меньшим значением.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Сколько нужно раундов

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

for _ in range(n - 1):
    relax_all_edges()

Инициализируйте расстояния

Начните со значения бесконечность для каждого расстояния, кроме расстояния до исходной вершины, равного нулю, — точно так же, как в алгоритме Дейкстры.

dist = [float('inf')] * n
dist[src] = 0

Один полный проход

Каждый проход один раз просматривает весь список рёбер и выполняет релаксацию каждого ребра. Улучшения распространяются на одну вершину дальше за каждый проход.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

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

После k проходов правильными становятся все кратчайшие пути, использующие k рёбер. После V-1 проходов завершается любой простой кратчайший путь.

Дополнительный проход

Выполните ещё один проход. Если какое-либо расстояние всё ещё уменьшается, стоимость продолжает снижаться, что указывает на отрицательный цикл.

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

Отрицательный цикл означает, что конечного кратчайшего пути не существует: можно бесконечно проходить по циклу и неограниченно уменьшать стоимость.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

Время работы

Вы выполняете релаксацию E рёбер за V проходов, поэтому алгоритм Беллмана — Форда работает за O(V * E) и подходит для небольших и средних графов.

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

Выбирайте алгоритм Дейкстры для неотрицательных весов и высокой скорости. Выбирайте алгоритм Беллмана — Форда, если появляются отрицательные веса или необходимо обнаружить отрицательный цикл.

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

После V-1 проходов расстояние всё ещё уменьшается во время ещё одного прохода. Что это означает?

Повторение: алгоритм Беллмана — Форда

Выполните релаксацию всех рёбер за V-1 проходов, а затем ещё один проход для обнаружения отрицательных циклов. Алгоритм работает за O(V*E), но справляется с задачами, где алгоритм Дейкстры не подходит. ✅

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

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

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

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

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

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

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

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

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

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

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

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

  1. Алгоритм Дейкстры с кучей
  2. 0-1 BFS с деком
  3. Беллман — Форд и отрицательные рёбра
  4. Алгоритм Флойда — Уоршелла для всех пар
← Назад к Coding Interview Prep