Кратчайший и длиннейший путь в DAG: топологическая сортировка за O(V + E)

Как найти кратчайший и самый длинный путь в ориентированном ациклическом графе за O(V + E): топологическая сортировка, релаксация рёбер, отрицательные веса, критический путь и связь с ДП.

12 мин чтенияграфы · алгоритмы · динамическое программирование · python

Коротко

ВопросОтвет
СложностьO(V+E)O(V + E) по времени, O(V)O(V) по памяти
Когда работаетграф ориентированный и без циклов (DAG)
Отрицательные весаможно, в отличие от Дейкстры
Главная идеяобходим вершины в топологическом порядке и релаксируем исходящие рёбра один раз
Длиннейший путьтот же алгоритм с max вместо min; в графе с циклами задача NP-трудна
Где встречаетсякритический путь проекта, расписания, LIS, почти любая ДП на «состояниях без циклов»

Для кратчайших путей в графе обычно вспоминают Дейкстру или Беллмана — Форда. Но если граф ациклический, оба избыточны: хватает одного прохода по вершинам в правильном порядке. Этот приём настолько простой, что его часто не замечают, а между тем на нём держится половина динамического программирования.

Почему в DAG всё проще

Ключевое свойство DAG: вершины можно выстроить в линию так, что все рёбра идут слева направо. Это и есть топологический порядок. Как его получить алгоритмом Кана или через DFS, подробно разобрано в статье про топологическую сортировку; здесь используем её как готовый кирпич.

Теперь представьте, что мы идём по вершинам в этом порядке. Когда очередь дошла до вершины uu, все рёбра, которые в неё входят, начинаются в вершинах левее. Их мы уже обработали. Значит, к этому моменту dist[u] окончательный: лучшего пути в uu не появится, потому что все возможные «последние шаги» в uu уже учтены.

Отсюда алгоритм:

  1. Получить топологический порядок.
  2. dist[src] = 0, остальные — бесконечность.
  3. Для каждой вершины uu в порядке сортировки и каждого ребра u→vu \to v веса ww: dist[v] = min(dist[v], dist[u] + w).

Это та же релаксация, что у Беллмана — Форда. Разница в том, что Беллман — Форд не знает правильного порядка и поэтому повторяет проход по всем рёбрам V−1V - 1 раз. Мы порядок знаем и обходимся одним проходом.

Формально это динамика:

dist(v)=min⁡(u,v)∈E(dist(u)+w(u,v))dist(v) = \min_{(u, v) \in E} \big( dist(u) + w(u, v) \big)

Топологический порядок гарантирует, что правая часть посчитана раньше левой. Если граф с циклом, такой гарантии нет: dist(v)dist(v) зависит от dist(u)dist(u), который зависит от dist(v)dist(v).

Наивные подходы и почему они хуже

Перебор всех путей через DFS. Число путей в DAG может быть экспоненциальным: в «лестнице» из nn ромбов их 2n2^n. Без мемоизации это не вариант. С мемоизацией — уже наш алгоритм, только записанный рекурсией.

Дейкстра. Работает за O((V+E)log⁡V)O((V + E) \log V), но только с неотрицательными весами. На DAG с отрицательным ребром она ошибается: вершину, извлечённую из кучи, Дейкстра считает готовой, а отрицательное ребро потом могло бы её улучшить.

# Граф: 0 -> 1 (2), 0 -> 2 (5), 2 -> 1 (-4). Правильный ответ для 1: 5 - 4 = 1 import heapq, math edges = [(0, 1, 2), (0, 2, 5), (2, 1, -4)] g = {0: [], 1: [], 2: []} for u, v, w in edges: g[u].append((v, w)) dist = {0: 0, 1: math.inf, 2: math.inf} done = set() pq = [(0, 0)] while pq: d, u = heapq.heappop(pq) if u in done: continue done.add(u) for v, w in g[u]: if v not in done and d + w < dist[v]: dist[v] = d + w heapq.heappush(pq, (dist[v], v)) print(dist) # {0: 0, 1: 2, 2: 5} — для вершины 1 ответ неверный

Беллман — Форд с отрицательными весами справится, но за O(V⋅E)O(V \cdot E). Подробнее о нём — в отдельной статье. На графе в сто тысяч вершин это разница между миллисекундами и минутами.

Кратчайший путь: код

Возьмём классический пример с шестью вершинами и отрицательными рёбрами:

0 ──5──► 1 0 ──3──► 2 1 ──6──► 3 1 ──2──► 2 2 ──4──► 4 2 ──2──► 5 2 ──7──► 3 3 ──(-1)──► 4 4 ──(-2)──► 5

Все рёбра идут от меньшего номера к большему, так что порядок 0, 1, 2, 3, 4, 5 топологический. Ищем пути из вершины 1.

from collections import deque import math def topo_order(n, graph): """Порядок Кана; None, если в графе есть цикл.""" indeg = [0] * n for u in range(n): for v, _ in graph[u]: indeg[v] += 1 queue = deque(u for u in range(n) if indeg[u] == 0) order = [] while queue: u = queue.popleft() order.append(u) for v, _ in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v) return order if len(order) == n else None def dag_shortest(n, edges, src): graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) order = topo_order(n, graph) if order is None: raise ValueError("граф не DAG") dist = [math.inf] * n parent = [-1] * n dist[src] = 0 for u in order: if dist[u] == math.inf: continue # до u из src не добраться for v, w in graph[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w parent[v] = u return dist, parent def restore(parent, target): path = [] while target != -1: path.append(target) target = parent[target] return path[::-1] edges = [ (0, 1, 5), (0, 2, 3), (1, 3, 6), (1, 2, 2), (2, 4, 4), (2, 5, 2), (2, 3, 7), (3, 4, -1), (4, 5, -2), ] dist, parent = dag_shortest(6, edges, 1) print(dist) # [inf, 0, 2, 6, 5, 3] print(restore(parent, 5)) # [1, 3, 4, 5]

Обратите внимание на continue для недостижимых вершин. Без него в Python ничего не сломается (inf + w остаётся inf), но в языках с целочисленной «бесконечностью» вроде INT_MAX сложение переполнится, и недостижимая вершина внезапно станет очень близкой.

Разбор по шагам

Топологический порядок для этого графа: 0, 1, 2, 3, 4, 5. Источник — вершина 1, поэтому вершина 0 остаётся с inf и пропускается.

ОбрабатываемРелаксацииdist после шага
0пропуск, dist[0] = inf[inf, 0, inf, inf, inf, inf]
12 ← 0+2 = 2, 3 ← 0+6 = 6[inf, 0, 2, 6, inf, inf]
24 ← 2+4 = 6, 5 ← 2+2 = 4, 3: 9 > 6[inf, 0, 2, 6, 6, 4]
34 ← 6-1 = 5[inf, 0, 2, 6, 5, 4]
45 ← 5-2 = 3[inf, 0, 2, 6, 5, 3]
5исходящих рёбер нет[inf, 0, 2, 6, 5, 3]

Кратчайший путь в 5 идёт через «дорогое» ребро 1→3, зато потом собирает два отрицательных. Жадный выбор ближайшего соседа, как у Дейкстры, его бы не нашёл.

Та же идея на JavaScript, с DFS

Порядок можно получить и через DFS: вершина добавляется в список после всех своих потомков, а потом список разворачивается. Заодно ловим цикл по «серым» вершинам — тем, что ещё в стеке рекурсии.

function dagShortestPaths(n, edges, src) { const graph = Array.from({ length: n }, () => []) for (const [u, v, w] of edges) graph[u].push([v, w]) // Топологический порядок через DFS: вершина попадает в список после всех потомков const state = new Array(n).fill(0) // 0 — не были, 1 — в стеке, 2 — готово const post = [] const dfs = (u) => { state[u] = 1 for (const [v] of graph[u]) { if (state[v] === 1) throw new Error('цикл: граф не DAG') if (state[v] === 0) dfs(v) } state[u] = 2 post.push(u) } for (let u = 0; u < n; u++) if (state[u] === 0) dfs(u) const order = post.reverse() const dist = new Array(n).fill(Infinity) dist[src] = 0 for (const u of order) { if (dist[u] === Infinity) continue for (const [v, w] of graph[u]) { if (dist[u] + w < dist[v]) dist[v] = dist[u] + w } } return dist } const edges = [ [0, 1, 5], [0, 2, 3], [1, 3, 6], [1, 2, 2], [2, 4, 4], [2, 5, 2], [2, 3, 7], [3, 4, -1], [4, 5, -2], ] console.log(dagShortestPaths(6, edges, 1)) // [ Infinity, 0, 2, 6, 5, 3 ]

На графах глубиной в десятки тысяч вершин рекурсивный DFS упрётся в лимит стека (в Python — по умолчанию около 1000 вызовов). На собеседовании безопаснее Кан: он итеративный и сразу говорит о цикле, если в порядок попали не все вершины.

Длиннейший путь

В произвольном графе задача о самом длинном простом пути NP-трудна: к ней сводится поиск гамильтонова пути. Но в DAG циклов нет, любой путь автоматически простой, и задача решается тем же проходом — меняем min на max, а начальное значение на минус бесконечность.

def dag_longest(n, edges, src): graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) order = topo_order(n, graph) if order is None: raise ValueError("граф не DAG") dist = [-math.inf] * n parent = [-1] * n dist[src] = 0 for u in order: if dist[u] == -math.inf: continue for v, w in graph[u]: if dist[u] + w > dist[v]: dist[v] = dist[u] + w parent[v] = u return dist, parent dist, parent = dag_longest(6, edges, 1) print(dist) # [-inf, 0, 2, 9, 8, 6] print(restore(parent, 5)) # [1, 2, 3, 4, 5]

Эквивалентный приём — умножить все веса на −1-1 и искать кратчайший путь. В DAG это законно именно потому, что отрицательные веса нам не страшны. В графе с циклами так делать нельзя: положительный цикл превратится в отрицательный, и «кратчайшего» пути не станет.

Длиннейший путь без фиксированного старта

Часто спрашивают не «от вершины ss», а «самый длинный путь в графе вообще». Тогда стартом может быть любая вершина: инициализируем dist нулями для всех и берём максимум в конце. С единичными весами это длина самой длинной цепочки зависимостей — например, минимальное число семестров, за которое можно пройти все курсы, если за семестр берётся сколько угодно курсов без незакрытых пререквизитов.

Критический путь проекта

Самое «бытовое» применение длиннейшего пути — метод критического пути (CPM). Задачи проекта — вершины, зависимости — рёбра, длительность — вес. Срок проекта равен самому длинному пути: быстрее, чем самая длинная цепочка зависимых задач, не управиться, сколько людей ни добавляй.

Два прохода по топологическому порядку дают всё, что нужно менеджеру:

  • прямой — самое раннее время старта каждой задачи;
  • обратный — самое позднее время старта, при котором дедлайн не сдвигается.

Разница между ними — запас (slack). Задачи с нулевым запасом лежат на критическом пути: любая их задержка двигает релиз.

from collections import deque def critical_path(duration, deps): """duration: {задача: дни}, deps: {задача: [от чего зависит]}.""" tasks = list(duration) children = {t: [] for t in tasks} indeg = {t: 0 for t in tasks} for t, before in deps.items(): for b in before: children[b].append(t) indeg[t] += 1 queue = deque(t for t in tasks if indeg[t] == 0) order = [] while queue: t = queue.popleft() order.append(t) for c in children[t]: indeg[c] -= 1 if indeg[c] == 0: queue.append(c) # Прямой проход: самое раннее время начала early = {t: 0 for t in tasks} for t in order: for c in children[t]: early[c] = max(early[c], early[t] + duration[t]) total = max(early[t] + duration[t] for t in tasks) # Обратный проход: самое позднее начало без сдвига дедлайна late = {t: total - duration[t] for t in tasks} for t in reversed(order): for c in children[t]: late[t] = min(late[t], late[c] - duration[t]) slack = {t: late[t] - early[t] for t in tasks} return total, early, slack duration = {"design": 3, "backend": 5, "frontend": 4, "db": 2, "tests": 3, "release": 1} deps = {"backend": ["design", "db"], "frontend": ["design"], "tests": ["backend", "frontend"], "release": ["tests"]} total, early, slack = critical_path(duration, deps) print("срок проекта:", total) for t in duration: mark = "крит." if slack[t] == 0 else f"запас {slack[t]}" print(f"{t:9} старт {early[t]:2} {mark}")
срок проекта: 12 design старт 0 крит. backend старт 3 крит. frontend старт 3 запас 1 db старт 0 запас 1 tests старт 8 крит. release старт 11 крит.

Критический путь — design → backend → tests → release, 3 + 5 + 3 + 1 = 12 дней. Фронтенд можно начать на день позже без последствий, а вот задержка бэкенда на день сдвигает релиз. Та же логика работает в системах сборки и оркестраторах задач: общее время пайплайна при неограниченном параллелизме — длиннейший путь в графе зависимостей.

Где прячется DAG: связь с динамическим программированием

Любая задача ДП — это кратчайший, длиннейший путь или подсчёт путей в DAG, вершины которого — состояния, а рёбра — переходы. Порядок заполнения таблицы и есть топологическая сортировка, просто её не нужно считать: она очевидна из индексов.

ЗадачаВершиныРёбраЧто ищем
Размен монетсуммы 0..amounts → s + coin, вес 1кратчайший путь 0 → amount
Лесенка (climbing stairs)ступениi → i+1, i → i+2число путей
Уникальные пути в сеткеклеткивправо и внизчисло путей
Наибольшая возрастающая подпоследовательностьиндексыi → j, если i < j и a[i] < a[j]длиннейший путь

Вот LIS, записанная как длиннейший путь. Топологическая сортировка не нужна: рёбра идут только от меньших индексов к большим.

def lis_as_dag(nums): # Вершины — индексы, ребро i -> j, если i < j и nums[i] < nums[j]. # Индексы уже идут в топологическом порядке, сортировать не нужно. n = len(nums) best = [1] * n # длина самого длинного пути, заканчивающегося в i for j in range(n): for i in range(j): if nums[i] < nums[j]: best[j] = max(best[j], best[i] + 1) return max(best, default=0) print(lis_as_dag([10, 9, 2, 5, 3, 7, 101, 18])) # 4

Подсчёт путей устроен так же, только вместо min/max — сумма:

def count_paths(n, edges, src, dst): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append((v, 1)) ways = [0] * n ways[src] = 1 for u in topo_order(n, graph): for v, _ in graph[u]: ways[v] += ways[u] return ways[dst] print(count_paths(5, [(0, 1), (0, 2), (1, 3), (2, 3), (1, 4), (3, 4)], 0, 4)) # 3

Этот взгляд полезен на собеседовании. Если вы видите задачу, где состояния зависят друг от друга без циклов, можно сразу сказать: «это путь в DAG, решаю проходом в топологическом порядке за O(V+E)O(V + E)». Когда же в «графе состояний» появляется цикл — например, клетки, по которым можно ходить во все стороны, — ДП в лоб не работает, и нужен BFS или Дейкстра.

Сложность

  • Построение списков смежности: O(V+E)O(V + E).
  • Топологическая сортировка: O(V+E)O(V + E).
  • Релаксация: каждое ребро рассматривается ровно один раз, O(E)O(E); каждая вершина — один раз, O(V)O(V).

Итого O(V+E)O(V + E) по времени и O(V)O(V) дополнительной памяти, не считая самого графа. Это асимптотически оптимально: прочитать граф быстрее нельзя.

Для сравнения на одном и том же DAG:

АлгоритмВремяОтрицательные веса
Проход по топологическому порядкуO(V+E)O(V + E)да
Дейкстра с кучейO((V+E)log⁡V)O((V + E) \log V)нет
Беллман — ФордO(V⋅E)O(V \cdot E)да
Флойд — Уоршелл (все пары)O(V3)O(V^3)да

Если нужны кратчайшие пути между всеми парами в DAG, запустите проход из каждой вершины: O(V⋅(V+E))O(V \cdot (V + E)). На разреженных графах это заметно быстрее Флойда.

Типичные ошибки

Забыли проверить ацикличность. Алгоритм молча выдаст мусор на графе с циклом: вершины цикла не попадут в порядок Кана, и их dist останутся бесконечными. Всегда сравнивайте длину порядка с nn.

Не пропустили недостижимые вершины. С INT_MAX или Number.MAX_SAFE_INTEGER вместо настоящей бесконечности сложение с отрицательным весом даст «конечное» расстояние для вершины, до которой пути нет. Для длиннейшего пути та же беда с минус бесконечностью.

Инициализировали все вершины нулём, хотя старт один. Для «длиннейшего пути из ss» это превращает задачу в «длиннейший путь, заканчивающийся где угодно». Ответ получится больше правильного.

Перепутали направление рёбер. Если в условии «курс B требует курс A», ребро идёт A → B. Обратное направление даёт обратный топологический порядок, и релаксация обрабатывает вершины до того, как их значения готовы.

Пытаются искать длиннейший путь Дейкстрой с max. Не работает даже на DAG: жадное «вершина готова, когда её извлекли» для максимума неверно. Используйте топологический порядок.

Путают DAG с деревом. В DAG у вершины может быть несколько родителей, поэтому один проход DFS от корня без мемоизации посчитает одни и те же поддеревья много раз.

Как это спрашивают на собеседованиях

Прямо «найдите кратчайший путь в DAG» спрашивают редко. Обычно задача замаскирована:

  • Расписание и зависимости. «Есть задачи с длительностями и зависимостями, за какое минимальное время можно всё сделать при неограниченном числе исполнителей?» Это критический путь. Вариант на LeetCode — Parallel Courses III.
  • Длиннейший возрастающий путь в матрице. Ребро из клетки в соседнюю с большим значением — граф ацикличен, потому что значения строго растут. Решается DFS с мемоизацией или Каном по полустепеням.
  • Цепочки слов и строк. «Самая длинная цепочка слов, где каждое следующее получено добавлением буквы» — сортировка по длине даёт топологический порядок.
  • Перелёты с ограничениями. Если время строго растёт вдоль пути, граф «событий» ацикличен, и вместо Дейкстры хватает прохода по времени.

Хороший ответ звучит так: «Состояния образуют DAG, потому что [величина] строго растёт вдоль рёбер. Значит, обрабатываю их в топологическом порядке и релаксирую рёбра, это O(V+E)O(V + E), отрицательные веса не мешают». Такая фраза показывает, что вы понимаете, почему работает решение, а не просто вспомнили шаблон.

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

Потренироваться в спокойной обстановке

Все задачи