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

Введение¶

В задачах на кратчайшие пути иногда возникает особая ситуация — в графе есть отрицательный цикл. Это цикл, сумма весов которого меньше нуля.

Такие циклы ломают классические алгоритмы: если можно бесконечно «крутиться» по циклу и уменьшать стоимость пути, то кратчайшего пути просто не существует.

В этом разделе мы разберём:

• что такое отрицательный цикл
• почему он опасен
• как его обнаруживать
• как это связано с алгоритмом Дейкстры

Что такое отрицательный цикл¶

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

Пример:

• A → B (вес 2)
• B → C (вес -5)
• C → A (вес 1)

Сумма: 2 + (-5) + 1 = -2

Это отрицательный цикл.

Почему это проблема¶

Если из стартовой вершины можно попасть в такой цикл, то:

• мы можем пройти цикл один раз → уменьшили путь
• два раза → ещё уменьшили
• бесконечно много раз → путь уходит в -∞

Следовательно:

кратчайшего пути не существует.

Связь с алгоритмом Дейкстры¶

Идея алгоритма Дейкстры¶

Алгоритм Дейкстры находит кратчайшие пути из одной вершины, если:

• все веса рёбер неотрицательные

Он работает так:

1. Храним расстояния до вершин
2. Каждый раз выбираем вершину с минимальным расстоянием
3. «Фиксируем» её — считаем, что её расстояние окончательное
4. Обновляем соседей

Почему важен выбор вершины¶

Ключевая идея:

Если мы выбрали вершину с минимальным расстоянием, то оно уже оптимально.

Почему?

Потому что:

• все рёбра неотрицательные
• значит любые альтернативные пути будут только длиннее

Почему алгоритм ломается¶

Если есть отрицательные рёбра:

• мы можем позже найти путь короче
• но вершина уже «зафиксирована»

Пример:

• A → B (10)
• A → C (1)
• C → B (-5)

Дейкстра сначала возьмёт B = 10 Но потом найдёт путь A → C → B = -4

Ошибка.

Вывод¶

• Дейкстра не работает с отрицательными весами
• и тем более с отрицательными циклами

Как обнаружить отрицательный цикл¶

Основной инструмент — алгоритм Беллмана-Форда

Идея¶

Если после n−1 итерации можно ещё улучшить расстояние — значит есть отрицательный цикл.

Алгоритм Беллмана-Форда (идея)¶

1. Инициализируем расстояния

2. Повторяем n−1 раз:

3. пытаемся улучшить все рёбра

4. Делаем ещё одну итерацию:

5. если что-то улучшилось → есть цикл

Пример¶

Граф:

A → B (1) B → C (1) C → A (-3)

Сумма цикла = -1

После нескольких итераций расстояния будут уменьшаться снова и снова.

Схема графа¶

mermaid graph LR A -->|1| B B -->|1| C C -->|-3| A

Реализация на C++¶

Простой вариант обнаружения цикла:

#include <iostream>
#include <vector>
using namespace std;

struct Edge {
    int a, b, w;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }

    vector<long long> d(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        bool changed = false;
        for (auto e : edges) {
            if (d[e.b] > d[e.a] + e.w) {
                d[e.b] = d[e.a] + e.w;
                changed = true;
            }
        }
        if (!changed) break;

        if (i == n && changed) {
            cout << "YES\n";
            return 0;
        }
    }

    cout << "NO\n";
}

Интуитивное объяснение¶

Каждая итерация «распространяет» информацию на 1 ребро дальше.

• за 1 шаг — пути длины 1
• за 2 — длины 2
• …
• за n−1 — все возможные пути

Если после этого улучшение всё ещё возможно — значит есть цикл.

Сложность¶

• Время: O(n · m)
• Память: O(n)

Простой пример с разбором¶

Граф:

1 → 2 (3) 2 → 3 (4) 3 → 2 (-6)

Шаги:

• сначала d[2] = 3
• потом d[3] = 7
• затем d[2] = 1
• потом d[3] = 5
• затем d[2] = -1

Расстояния уменьшаются бесконечно → цикл есть

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

Используй обнаружение отрицательных циклов, если:

• есть отрицательные веса
• нужно проверить корректность графа
• задача явно говорит про «бесконечно уменьшающиеся пути»
• используешь Беллмана-Форда

Типичные ошибки¶

1. Использование Дейкстры при отрицательных рёбрах¶

Это приводит к неверным ответам.

2. Проверка только из одной вершины¶

Цикл может быть в другой компоненте.

Решение:

• либо запускать из всех вершин
• либо инициализировать все расстояния нулями

3. Переполнение¶

Используй long long для расстояний.

4. Ранний выход¶

Если алгоритм остановился раньше — это нормально Но цикл проверяется только на n-й итерации

Итог¶

• Отрицательный цикл означает отсутствие кратчайшего пути
• Дейкстра не работает с отрицательными весами
• Беллман-Форд позволяет обнаружить цикл
• Проверка: есть ли улучшение на n-й итерации

Это один из ключевых инструментов в задачах на графы и часто встречается в олимпиадных задачах.