Информатика · объяснение и практика
Как ослабление рёбер работает с отрицательными весами
Разбираем последовательное улучшение расстояний, влияние порядка рёбер и проверку достижимого отрицательного цикла на собственном примере.

В теме Графы и маршруты · Учебная карта
Главная мысль
Ослабить ребро u→v — значит проверить, не короче ли путь через u, и при необходимости уменьшить расстояние до v. Беллман — Форд повторяет проверки всех рёбер, поэтому допускает отрицательные веса при отсутствии влияющего отрицательного цикла.
Одна проверка ещё не заканчивает маршрут
Возьмём дуги С→А веса 5, А→Б веса −3 и С→Б веса 8. Стартуем в С: до него расстояние 0, остальные вершины пока недостижимы. Если сначала обработать А→Б, улучшения не будет: путь до А ещё не найден. Затем С→А даст 5, а С→Б — 8.
Во втором проходе дуга А→Б уменьшит расстояние до Б до 2. При другом порядке рёбер число 2 могло появиться уже в первом проходе. Поэтому результат одного прохода нельзя оценивать по самому удачному порядку: гарантия алгоритма рассчитана и на неудобное расположение рёбер.
Пример
После первого прохода в указанном порядке: С=0, А=5, Б=8. После второго: Б=2.
Проверка использует только уже достижимый хвост дуги. Метка недостижимости не является большим обычным числом, из которого разрешено вычитать вес.
Почему достаточно n−1 основных проходов
Если отрицательного цикла на нужных маршрутах нет, можно выбрать кратчайший путь без повторяющихся вершин. В графе из n вершин у него не более n−1 ребра. Каждый полный проход гарантированно передаёт правильную оценку ещё хотя бы на одно ребро вдоль такого пути.
Значит, после n−1 проходов все конечные расстояния из источника установлены. Обновление внутри прохода иногда продвигается дальше, но это ускорение, а не обязательное условие доказательства. Если за полный проход не случилось ни одного изменения, можно завершить вычисления раньше.
Дополнительный проход служит другой цели
После основных проходов проверяют, осталось ли достижимое ребро, которое ещё улучшает расстояние. Если осталось, из источника достижим отрицательный цикл. Однако это не означает, что любая вершина графа потеряла конечный ответ: важна достижимость от цикла к рассматриваемой цели.
Если добавить к нашему примеру Б→А веса 1, цикл А→Б→А получит вес −2. Расстояния до А и Б можно уменьшать бесконечно, но до отдельной недостижимой вершины Т путь от этого не появится. Сохраняйте в выводе различие между конечным расстоянием, недостижимостью и влиянием отрицательного цикла.
От чтения к действию
А теперь — вы
Частые вопросы
Найдёт ли один запуск отрицательный цикл в отдельной компоненте?
При старте из одного источника — нет, если компоненту нельзя достичь. Для проверки всего графа нужна другая инициализация, например дополнительный источник с нулевыми дугами ко всем вершинам.
Почему не остановиться сразу после отрицательного ребра?
Отрицательное ребро может просто сделать маршрут выгоднее. Неограниченное уменьшение возникает при повторяемом отрицательном цикле, а не из-за знака одной дуги.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему алгоритму Дейкстры нужны неотрицательные веса
Находим кратчайшие стоимости при неотрицательных весах, различаем предварительную оценку и окончательную вершину и показываем точную причину ограничения на отрицательные рёбра.
Открыть темуКак промежуточная вершина обновляет расстояния между всеми парами
На небольшом ориентированном графе строим таблицу расстояний, добавляем разрешённые промежуточные вершины и отдельно проверяем отрицательные циклы.
Открыть тему