Как работает Беллман-Форд и как им обнаружить отрицательный цикл?
Нужно найти кратчайшие пути в графе с отрицательными рёбрами и заодно понять, есть ли отрицательный цикл (тогда ответа нет). Слышал про Беллман-Форд. Как он устроен, почему именно V-1 итераций и как ловить отрицательный цикл?
2 ответа
Идея: кратчайший путь без циклов содержит не более V-1 рёбер. Делаем V-1 проходов по всем рёбрам, на каждом проходе релаксируем. После i проходов гарантированно правильно посчитаны все кратчайшие пути из i рёбер. Значит после V-1 проходов всё посчитано.
using ll = long long;
const ll INF = 1e18;
struct Edge { int u, v; ll w; };
vector<Edge> edges;
vector<ll> dist(n, INF);
dist[s] = 0;
for (int i = 0; i < n - 1; i++)
for (auto& e : edges)
if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v])
dist[e.v] = dist[e.u] + e.w;
// проверка отрицательного цикла:
bool hasNegCycle = false;
for (auto& e : edges)
if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v])
hasNegCycle = true;
Сложность O(V·E) по времени, O(V) по памяти. Если на V-й (дополнительной) итерации что-то ещё релаксируется — значит есть отрицательный цикл, достижимый из s.
Два важных уточнения. Первое: проверка dist[e.u] < INF обязательна — иначе INF + w переполнит long long и из недостижимой вершины «утечёт» ложная релаксация. Второе: чтобы найти сами вершины, лежащие на отрицательном цикле (а не просто факт его наличия), запоминайте parent[] и на V-й итерации от срелаксированной вершины пройдите назад по предкам V раз — попадёте в цикл. Это нужно, например, в задачах «найти арбитраж» на валютном графе.