Беллман — Форд: как найти путь с отрицательными весами

Интерактивный разбор Беллмана — Форда: https://grundyjs.ru/algorithms/bellman-ford/?utm_source=rutube&utm_medium=social&utm_campaign=bellman_ford&utm_content=horizontal Беллман — Форд ищет минимальную стоимость пути в ориентированном графе, в том числе с отрицательными весами. На каждом проходе проверяет все рёбра: если d(u) + вес меньше d(v), обновляет расстояние и предка. В исходном примере четыре вершины и три основных прохода. После первого прохода d(A) = 2, d(B) = 5. Во втором цель сначала получает оценку 4, а отрицательное ребро B → A улучшает A до 1. На третьем проходе стоимость до цели уменьшается до 3. Итоговый путь S → B → A → G: 5 − 4 + 2 = 3. После основных проходов выполняется отдельная контрольная проверка. Если достижимую оценку всё ещё можно улучшить, есть отрицательный цикл, достижимый от старта. Добавим A → B с весом 3: цикл A → B → A стоит 3 − 4 = −1. Каждый круг уменьшает стоимость. Из цикла можно попасть в G, поэтому для цели нет конечного минимума: d(G) = −∞. Недостижимый от старта цикл X ↔ Y на ответ не влияет: путь к G по-прежнему стоит 3. Отрицательное ребро само по себе не означает отрицательного цикла. Если достижимый цикл не ведёт к выбранной цели, стоимость до этой цели может оставаться конечной. На первой найденной оценке цели останавливать алгоритм нельзя. В интерактивном разборе можно пройти алгоритм по шагам, изменить вес ребра, выбрать старт и цель, сравнить пять примеров и поделиться своим графом. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #БеллманФорд #графы #программирование