Кратчайший и длиннейший путь в DAG: топологическая сортировка за O(V + E)
Как найти кратчайший и самый длинный путь в ориентированном ациклическом графе за O(V + E): топологическая сортировка, релаксация рёбер, отрицательные веса, критический путь и связь с ДП.
Коротко
| Вопрос | Ответ |
|---|---|
| Сложность | по времени, по памяти |
| Когда работает | граф ориентированный и без циклов (DAG) |
| Отрицательные веса | можно, в отличие от Дейкстры |
| Главная идея | обходим вершины в топологическом порядке и релаксируем исходящие рёбра один раз |
| Длиннейший путь | тот же алгоритм с max вместо min; в графе с циклами задача NP-трудна |
| Где встречается | критический путь проекта, расписания, LIS, почти любая ДП на «состояниях без циклов» |
Для кратчайших путей в графе обычно вспоминают Дейкстру или Беллмана — Форда. Но если граф ациклический, оба избыточны: хватает одного прохода по вершинам в правильном порядке. Этот приём настолько простой, что его часто не замечают, а между тем на нём держится половина динамического программирования.
Почему в DAG всё проще
Ключевое свойство DAG: вершины можно выстроить в линию так, что все рёбра идут слева направо. Это и есть топологический порядок. Как его получить алгоритмом Кана или через DFS, подробно разобрано в статье про топологическую сортировку; здесь используем её как готовый кирпич.
Теперь представьте, что мы идём по вершинам в этом порядке. Когда очередь дошла до вершины , все рёбра, которые в неё входят, начинаются в вершинах левее. Их мы уже обработали. Значит, к этому моменту dist[u] окончательный: лучшего пути в не появится, потому что все возможные «последние шаги» в уже учтены.
Отсюда алгоритм:
- Получить топологический порядок.
dist[src] = 0, остальные — бесконечность.- Для каждой вершины в порядке сортировки и каждого ребра веса :
dist[v] = min(dist[v], dist[u] + w).
Это та же релаксация, что у Беллмана — Форда. Разница в том, что Беллман — Форд не знает правильного порядка и поэтому повторяет проход по всем рёбрам раз. Мы порядок знаем и обходимся одним проходом.
Формально это динамика:
Топологический порядок гарантирует, что правая часть посчитана раньше левой. Если граф с циклом, такой гарантии нет: зависит от , который зависит от .
Наивные подходы и почему они хуже
Перебор всех путей через DFS. Число путей в DAG может быть экспоненциальным: в «лестнице» из ромбов их . Без мемоизации это не вариант. С мемоизацией — уже наш алгоритм, только записанный рекурсией.
Дейкстра. Работает за , но только с неотрицательными весами. На 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 ответ неверный
Беллман — Форд с отрицательными весами справится, но за . Подробнее о нём — в отдельной статье. На графе в сто тысяч вершин это разница между миллисекундами и минутами.
Кратчайший путь: код
Возьмём классический пример с шестью вершинами и отрицательными рёбрами:
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] |
| 1 | 2 ← 0+2 = 2, 3 ← 0+6 = 6 | [inf, 0, 2, 6, inf, inf] |
| 2 | 4 ← 2+4 = 6, 5 ← 2+2 = 4, 3: 9 > 6 | [inf, 0, 2, 6, 6, 4] |
| 3 | 4 ← 6-1 = 5 | [inf, 0, 2, 6, 5, 4] |
| 4 | 5 ← 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]
Эквивалентный приём — умножить все веса на и искать кратчайший путь. В DAG это законно именно потому, что отрицательные веса нам не страшны. В графе с циклами так делать нельзя: положительный цикл превратится в отрицательный, и «кратчайшего» пути не станет.
Длиннейший путь без фиксированного старта
Часто спрашивают не «от вершины », а «самый длинный путь в графе вообще». Тогда стартом может быть любая вершина: инициализируем 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..amount | s → 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, решаю проходом в топологическом порядке за ». Когда же в «графе состояний» появляется цикл — например, клетки, по которым можно ходить во все стороны, — ДП в лоб не работает, и нужен BFS или Дейкстра.
Сложность
- Построение списков смежности: .
- Топологическая сортировка: .
- Релаксация: каждое ребро рассматривается ровно один раз, ; каждая вершина — один раз, .
Итого по времени и дополнительной памяти, не считая самого графа. Это асимптотически оптимально: прочитать граф быстрее нельзя.
Для сравнения на одном и том же DAG:
| Алгоритм | Время | Отрицательные веса |
|---|---|---|
| Проход по топологическому порядку | да | |
| Дейкстра с кучей | нет | |
| Беллман — Форд | да | |
| Флойд — Уоршелл (все пары) | да |
Если нужны кратчайшие пути между всеми парами в DAG, запустите проход из каждой вершины: . На разреженных графах это заметно быстрее Флойда.
Типичные ошибки
Забыли проверить ацикличность. Алгоритм молча выдаст мусор на графе с циклом: вершины цикла не попадут в порядок Кана, и их dist останутся бесконечными. Всегда сравнивайте длину порядка с .
Не пропустили недостижимые вершины. С INT_MAX или Number.MAX_SAFE_INTEGER вместо настоящей бесконечности сложение с отрицательным весом даст «конечное» расстояние для вершины, до которой пути нет. Для длиннейшего пути та же беда с минус бесконечностью.
Инициализировали все вершины нулём, хотя старт один. Для «длиннейшего пути из » это превращает задачу в «длиннейший путь, заканчивающийся где угодно». Ответ получится больше правильного.
Перепутали направление рёбер. Если в условии «курс B требует курс A», ребро идёт A → B. Обратное направление даёт обратный топологический порядок, и релаксация обрабатывает вершины до того, как их значения готовы.
Пытаются искать длиннейший путь Дейкстрой с max. Не работает даже на DAG: жадное «вершина готова, когда её извлекли» для максимума неверно. Используйте топологический порядок.
Путают DAG с деревом. В DAG у вершины может быть несколько родителей, поэтому один проход DFS от корня без мемоизации посчитает одни и те же поддеревья много раз.
Как это спрашивают на собеседованиях
Прямо «найдите кратчайший путь в DAG» спрашивают редко. Обычно задача замаскирована:
- Расписание и зависимости. «Есть задачи с длительностями и зависимостями, за какое минимальное время можно всё сделать при неограниченном числе исполнителей?» Это критический путь. Вариант на LeetCode — Parallel Courses III.
- Длиннейший возрастающий путь в матрице. Ребро из клетки в соседнюю с большим значением — граф ацикличен, потому что значения строго растут. Решается DFS с мемоизацией или Каном по полустепеням.
- Цепочки слов и строк. «Самая длинная цепочка слов, где каждое следующее получено добавлением буквы» — сортировка по длине даёт топологический порядок.
- Перелёты с ограничениями. Если время строго растёт вдоль пути, граф «событий» ацикличен, и вместо Дейкстры хватает прохода по времени.
Хороший ответ звучит так: «Состояния образуют DAG, потому что [величина] строго растёт вдоль рёбер. Значит, обрабатываю их в топологическом порядке и релаксирую рёбра, это , отрицательные веса не мешают». Такая фраза показывает, что вы понимаете, почему работает решение, а не просто вспомнили шаблон.
Для тренировки начните с задач на ДП ниже: в каждой из них попробуйте нарисовать граф состояний и увидеть, какой путь вы на самом деле ищете.