Пути на ДАГе: один проход в топологическом порядке

Коротко

Если граф ациклический, задача становится резко проще: достаточно обойти вершины в топологическом порядке и релаксировать исходящие рёбра каждой - по одному разу. Цена O(V + E), веса любые, включая отрицательные, и никакой кучи не нужно. Работает это потому, что в топологическом порядке все пути в вершину приходят «слева»: к моменту, когда мы её обрабатываем, все рёбра, ведущие в неё, уже релаксированы, и оценка окончательна. Бонусом получается то, чего в общем графе не бывает: самый ДЛИННЫЙ путь на ДАГе тоже ищется за O(V + E) - меняем минимум на максимум. В произвольном графе эта задача NP-трудна - то есть быстрого (полиномиального) алгоритма для неё не знают, и большинство считает, что его нет: самый длинный простой путь по всем вершинам - это гамильтонов путь, одна из известных трудных задач. Разница ровно в отсутствии циклов.

Если ты знаешь алгоритм «топологический порядок плюс одна релаксация на ребро», понимаешь, почему оценка окончательна, и помнишь про длиннейшие пути и критический путь, листай до «Теперь сам».

Как думаешь, зачем тут вообще алгоритм

Мы уже умеем считать топологический порядок и умеем релаксировать. Прежде чем читать дальше, сложи два и два: если обрабатывать вершины ровно в топологическом порядке, сколько раз придётся релаксировать каждое ребро, чтобы все расстояния стали верными? И почему на ациклическом графе отрицательные веса перестают быть проблемой?

На что это похоже

Сборка изделия по технологической карте. Деталь нельзя ставить, пока не готовы все её комплектующие, - и карта как раз выстроена так, чтобы к моменту установки всё нужное уже лежало рядом. Посчитать «самый ранний срок готовности каждой детали» можно за один проход по карте сверху вниз: у каждой детали берём максимум сроков её комплектующих плюс время сборки.

Механизм: топологический порядок плюс один проход

def dag_shortest(start):
    dist = [INF] * V
    dist[start] = 0
    for v in topological_order:            # порядок из главы про топологическую сортировку
        if dist[v] == INF:
            continue                       # вершина недостижима - релаксировать нечего
        for (u, w) in adj[v]:
            if dist[v] + w < dist[u]:
                dist[u] = dist[v] + w
                prev[u] = v
    return dist

Каждое ребро релаксируется ровно один раз - когда обрабатывается его начало. Итого O(V + E) на сам проход плюс O(V + E) на топологическую сортировку.

Самый длинный путь - тот же код с перевёрнутым сравнением:

кратчайший путь : dist[u] = min(dist[u], dist[v] + w)   старт: 0, остальные +∞
длиннейший путь : dist[u] = max(dist[u], dist[v] + w)   старт: 0, остальные −∞
                  (в коде −∞ - это, как и INF, просто число: NEG = -1000000;
                   можно и проще - взять веса с минусом и искать минимум)

Второй вариант в общем графе не работает вовсе: там задача о самом длинном ПРОСТОМ пути NP-трудна (если бы мы умели решать её быстро, умели бы и находить гамильтонов путь). На ДАГе она решается за линию, и причина ровно одна - циклов нет, а значит нет и соблазна накручивать их ради длины.

Правило

На ациклическом графе кратчайшие пути считаются за O(V + E): обойти вершины в топологическом порядке и релаксировать исходящие рёбра каждой по одному разу. Веса любые, включая отрицательные; куча не нужна. Оценка вершины окончательна к моменту её обработки, потому что все ведущие в неё рёбра идут от вершин, стоящих в порядке раньше. Заменив min на max, тем же кодом получаем ДЛИННЕЙШИЙ путь - на ДАГе это линейно, в произвольном графе NP-трудно.

Разбор: почему оценка уже окончательна

Возьмём вершину u и момент, когда алгоритм до неё дошёл. Любой путь из s в u заканчивается каким-то ребром x → u. В топологическом порядке начало ребра стоит раньше конца, значит x была обработана РАНЬШЕ u - а при обработке x мы релаксировали ребро x → u.

Дальше индукция по позиции в порядке: если для всех вершин левее u оценки уже окончательны, то и dist[u] окончательна, потому что она получилась минимумом по всем входящим рёбрам от вершин, чьи оценки верны. База - стартовая вершина с нулём.

Обрати внимание, чего в этом рассуждении НЕТ: ни слова про знак весов. Именно поэтому на ДАГе отрицательные веса ничего не ломают - оптимальный порядок обработки известен заранее из структуры графа, а не выводится из значений dist, как у Дейкстры. И отрицательных циклов тоже быть не может: циклов нет вовсе.

Разбор: критический путь в плане работ

Задача из практики: есть работы с длительностями и зависимости «эту после той». Когда закончится проект и какие работы нельзя задерживать?

Строим ДАГ: вершина - работа, ребро A → B означает «B после A», вес ребра - длительность A. Самый длинный путь от начала до конца и есть критический путь: его длина равна минимально возможному сроку проекта, а работы на нём не имеют запаса - задержка любой сдвигает весь срок.

Чтобы в сумму попала длительность ПОСЛЕДНЕЙ работы, к графу добавляют две фиктивные вершины - «начало» и «конец»: из начала в каждую работу без зависимостей ведёт ребро веса 0, а из каждой работы без продолжений - ребро в конец весом её длительности.

работы и длительности:  A(3), B(5), C(2), D(4)
зависимости:            A → C,   B → C,   C → D
вес ребра = длительность его НАЧАЛА

начало →(0) A →(3) C →(2) D →(4) конец
начало →(0) B →(5) C

самый длинный путь: начало → B → C → D → конец = 0 + 5 + 2 + 4 = 11 дней
путь через A:       начало → A → C → D → конец = 0 + 3 + 2 + 4 =  9 дней
                    → у работы A есть запас в 2 дня

Считается это тем же одним проходом по топологическому порядку с max вместо min. В главе про топологическую сортировку мы считали ЧИСЛО уровней - это частный случай: все длительности равны единице. Теперь длительности произвольные, и ответ получается таким же линейным проходом.

Отсюда же и практический вывод, который стоит унести: увидев в задаче слова «планирование», «зависимости», «самый ранний/поздний срок», ищи ДАГ - и считай один проход, а не запускай Дейкстру.

Что ломается без этого

Первое: применить метод к графу с циклом - топологического порядка не существует, и алгоритм просто не определён; проверку на цикл делают заранее (она же бесплатна при построении порядка). Второе: забыть пропуск недостижимых вершин (dist[v] == INF) - и получить «бесконечность плюс вес» в оценках соседей. Третье: искать длиннейший путь в произвольном графе тем же приёмом - задача NP-трудна, и линейного решения не существует; на графе с циклом положительного веса «длиннейшего» не существует вовсе, как не существует кратчайшего при отрицательном цикле. Четвёртое: считать, что для ДАГа годится и Дейкстра - годится, но она дороже (log на операцию) и запрещает отрицательные веса; на ДАГе нет причин её использовать. Пятое: путать топологический порядок с порядком по номерам вершин: он совпадает только если граф специально так пронумерован.

Зачем это в работе

Планирование проектов и сборок: критический путь, самые ранние и самые поздние сроки, запас по каждой работе - всё это один проход по ДАГу (метод так и называется - сетевое планирование, PERT и CPM). Компиляторы и системы сборки считают по ДАГу порядок и стоимость шагов. Динамическое программирование - это вообще всегда путь по ДАГу подзадач: «посчитать значение через уже посчитанные» буквально означает релаксацию в топологическом порядке, и потому многие задачи ДП удобно видеть как поиск самого длинного или самого короткого пути. А практическая привычка простая: прежде чем брать Дейкстру, проверь, нет ли в графе циклов - если нет, ты сэкономишь и логарифм, и ограничение на знак весов.

Теперь сам

ДАГ: s→a = 3, s→b = 1, a→c = −2, b→c = 4, c→t = 2, топологический порядок s, a, b, c, t. Посчитай кратчайшие расстояния одним проходом. Затем посчитай ДЛИННЕЙШИЕ пути от s и скажи, какая работа лежит на критическом пути.

Ответ. Кратчайшие. Начало: dist[s] = 0, остальные +∞. Обрабатываем s: s→a: dist[a] = 3; s→b: dist[b] = 1. Обрабатываем a: a→c: 3 + (−2) = 1 → dist[c] = 1. Обрабатываем b: b→c: 1 + 4 = 5 < 1? нет - оценка не меняется. Обрабатываем c: c→t: 1 + 2 = 3 → dist[t] = 3. Итог: dist = {s:0, a:3, b:1, c:1, t:3}, маршрут до t - s → a → c → t. Каждое ребро тронули ровно один раз, отрицательный вес −2 не потребовал ничего особенного.

Длиннейшие. Тот же массив оценок, но теперь он хранит не «самый дешёвый», а «самый дорогой» путь; назову его far, чтобы не путать с dist выше. Начало: far[s] = 0, остальные −∞. s: far[a] = 3, far[b] = 1. a: a→c: 3 − 2 = 1 → far[c] = 1. b: b→c: 1 + 4 = 5 > 1 → far[c] = 5. c: c→t: 5 + 2 = 7 → far[t] = 7. Итог: самый длинный путь равен 7 по маршруту s → b → c → t. Обрати внимание: кратчайший и длиннейший пути пошли РАЗНЫМИ дорогами (через a и через b соответственно), и критическим - тем, который определяет срок, - оказался путь через b. Значит задержка работы b сдвинет весь проект, а у работы a есть запас.

Главное

На ациклическом графе кратчайшие пути считаются одним проходом в ТОПОЛОГИЧЕСКОМ порядке: каждое ребро релаксируется ровно один раз, цена O(V + E), куча не нужна, веса любые - включая отрицательные. Корректность следует из порядка, а не из значений: все рёбра, ведущие в вершину, идут от вершин, стоящих раньше, значит к моменту обработки её оценка окончательна (индукция по позиции в порядке; про знак весов в рассуждении нет ни слова). Заменив min на max, тем же кодом получаем ДЛИННЕЙШИЙ путь - на ДАГе это линейно, а в произвольном графе задача NP-трудна. Именно так считают критический путь в планировании: длина самого длинного пути - минимальный срок проекта, а работы на нём не имеют запаса. Частный случай с единичными весами мы уже видели - это уровни параллельности из алгоритма Кана. Общая привычка: прежде чем брать Дейкстру, проверь, нет ли циклов; если их нет, проход по топологическому порядку и дешевле, и свободнее по весам.