Как восстановить отрицательный цикл, а не только узнать, что он есть?
Беллман-Форд говорит мне «есть отрицательный цикл», но в задаче нужно вывести сами вершины этого цикла (например, последовательность валют для арбитража). Как из релаксации вытащить конкретный цикл?
2 ответа
Запоминаем предков par[] при релаксации. Делаем V итераций Беллмана-Форда; если на V-й итерации какая-то вершина x всё ещё релаксируется — она достижима из отрицательного цикла (но сама может в нём не лежать). Чтобы точно попасть в цикл, прыгаем по предкам V раз — гарантированно окажемся внутри цикла. Дальше идём по предкам, пока не вернёмся в ту же вершину.
int x = -1;
for (int i = 0; i < n; i++) {
x = -1;
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;
par[e.v] = e.u;
x = e.v; // запомнили срелаксированную вершину
}
}
if (x != -1) {
for (int i = 0; i < n; i++) x = par[x]; // войти в цикл
vector<int> cycle;
for (int v = x; ; v = par[v]) {
cycle.push_back(v);
if (v == x && cycle.size() > 1) break;
}
reverse(cycle.begin(), cycle.end());
}
Сложность O(V·E) — обычный Беллман-Форд. Прыжок V раз по предкам нужен именно чтобы выйти из «хвоста» в сам цикл.
Чтобы искать цикл, достижимый из ЛЮБОЙ вершины (а не только из конкретного старта), инициализируйте dist[] = 0 для всех вершин — это эквивалентно добавлению фиктивного источника, ведущего ко всем (как в Джонсоне). Тогда Беллман-Форд найдёт отрицательный цикл в любой компоненте. Классическое применение — арбитраж на валютах: берём логарифмы курсов с минусом, отрицательный цикл = возможность бесконечно богатеть.