Где применяется
1. Задача
Шаг 97 дал тебе Дейкстру, быстрый способ искать кратчайшие пути во взвешенном графе. У него есть одно условие: вес каждого ребра должен быть нулём или больше. Дейкстра закрепляет расстояние узла, как только достаёт его из кучи, и больше к нему не возвращается. Это безопасно, только если ни одно ребро, до которого дело дойдёт позже, не может сделать путь дешевле. Отрицательное ребро нарушает это условие. Дорога, до которой ты доберёшься поздно, ещё может понизить расстояние, а Дейкстра уже ушёл дальше.
Теперь у тебя ориентированный граф, и часть его рёбер стоит отрицательную величину: скидка, возврат денег, кредит. Тебе по-прежнему нужно кратчайшее расстояние от одного стартового узла до каждого другого. Ещё нужно понять, когда у задачи вообще нет ответа. Если есть петля из рёбер, сумма весов которой меньше нуля, по ней можно ходить по кругу без конца, и путь будет становиться всё дешевле. Тогда «кратчайшего» пути просто нет.
Алгоритм Беллмана-Форда решает обе задачи. Он работает с отрицательными рёбрами и сообщает, когда достижимая петля с отрицательной суммой лишает задачу ответа.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на кратчайший путь с отрицательными рёбрами или с лимитом на число рёбер в пути. Беллман-Форд делает релаксацию всех рёбер раундами, и после k раундов готовы все пути длиной до k рёбер.
Сделай ровно k + 1 раундов и делай релаксацию от копии расстояний прошлого раунда, тогда путь не возьмёт больше перелётов, чем разрешено.
Обычно тут берут Дейкстру, но при n не больше 100 bellmanFord из урока тоже проходит.
- 1334.Find the City With the Smallest Number of Neighbors at a Threshold Distance (откроется в новой вкладке)Средняя
Запусти Беллмана-Форда от каждого города и обрывай запуск, когда раунд ничего не изменил, потом посчитай города в пределах порога.