Motivation
Урок 2 из 9 курса Алгоритм Беллмана-Форда — Алгоритмы на графах на Coddy.
Алгоритм Беллмана-Форда основан на одной операции — релаксации: для ребра u -> v весом w, если путь через u дешевле (dist[u] + w < dist[v]), обновите dist[v]. Повторяйте это для каждого ребра.
Зачем изучать алгоритм Беллмана-Форда?
- Отрицательные веса: он работает там, где алгоритм Дейкстры бессилен, например, когда стоимость может быть скидкой или при валютном арбитраже.
- Обнаружение отрицательных циклов: один дополнительный проход релаксации выявляет циклы, суммарный вес которых отрицателен.
- Простота: не требуется очередь с приоритетом, только повторная релаксация ребер.
Компромисс заключается в скорости: O(V * E), что медленнее, чем O((V + E) log V) у алгоритма Дейкстры.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
