Как найти кратчайший путь в DAG за O(V+E) через топологическую сортировку?
Граф ориентированный и ацикличный (DAG), веса любые (в том числе отрицательные). Дейкстра отпадает из-за отрицательных весов, Беллман-Форд O(V·E) медленный. Слышал, что на DAG можно за линию. Как?
2 ответа
На DAG нет циклов, поэтому существует топологический порядок. Если обрабатывать вершины в этом порядке и релаксировать их рёбра, то к моменту обработки вершины её расстояние уже финально (все предшественники обработаны). Отрицательные веса не мешают — циклов-то нет.
// topo — вершины в топологическом порядке (например, через Кана или DFS)
vector<ll> dist(n, INF);
dist[s] = 0;
for (int v : topo) {
if (dist[v] == INF) continue;
for (auto [u, w] : g[v])
if (dist[v] + w < dist[u])
dist[u] = dist[v] + w;
}
Сложность O(V + E) по времени (топосорт + один проход), O(V) памяти. Это самый быстрый способ для DAG и единственный линейный при отрицательных весах. Заодно так же ищут самый длинный путь в DAG — поменяв min на max.
Длинный путь в DAG — частая олимпиадная задача (критический путь, schedule). Обычный «longest path» в произвольном графе NP-трудный, но на DAG он решается этой же схемой за O(V+E), просто релаксируя на максимум. Если граф вдруг оказался не DAG (есть цикл), топосорт через алгоритм Кана это обнаружит — в очередь попадёт меньше V вершин.