Подсчёт путей в ДАГ

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 24 · страница 24.3
Подсчёт путей в ДАГ
Топологическая сортировка (Кана) + динамическое программирование + критический путь.
Для ДАГ число путей считается за O(V+E) — топологически сортируем вершины, потом DP от старта. Тот же метод используется для
критического пути
в управлении проектами.
ФГОС
ФОП
ЕГЭ №1
углубл.
01
Топологическая сортировка (алгоритм Кана)
Топологическая сортировка — это линейная упорядоченная расстановка вершин Directed Acyclic Graph (DАГ) так, что для каждого ребра u→v вершина u стоит раньше v. Она является фундаментом для DP на графах.
Алгоритм Кана: пошагово
Подсчитать in-degree
каждой вершины — число рёбер, входящих в неё.
Инициализировать очередь
— поместить в неё все вершины с in-degree = 0 (истоки).
Извлечь u
из очереди, добавить в конец результата (топсорт-порядок).
Уменьшить in-degree
для каждого соседа v ребра u→v. Если in-degree[v] стал равен 0 — добавить v в очередь.
Повторять
шаги 3–4, пока очередь не пуста.
Проверка:
если в результате fewer вершин, чем в графе — значит граф содержит цикл (топсорт невозможен).
Сложность
O(V + E)
— каждая вершина и каждое ребро обрабатываются ровно один раз. В реализации используется очередь (_FIFO_), но допустим и стек.
Пример на графе из 7 вершин
Шаг 1:
in-degree: A=0, B=1, C=1, D=2, E=2, F=1, G=4
Шаг 2:
Очередь: [A]
Шаг 3:
Извлекаем A → результат: [A]
Шаг 4:
A→B, A→C: in-degree B=0, C=0 → очередь: [B, C]
Шаг 3:
Извлекаем B → результат: [A, B]
Шаг 4:
B→D, B→E: in-degree D=1, E=1
Шаг 3:
Извлекаем C → результат: [A, B, C]
Шаг 4:
C→E, C→F: in-degree E=0, F=0 → очередь: [E, F]
…
продолжаем до G
Итог:
A → B → C → E → F → D → G (один из вариантов)
Зачем нужен топсорт?
Он гарантирует, что при обходе вершин в полученном порядке все предки каждой вершины уже обработаны — именно это нужно для корректного DP.
02
DP для подсчёта путей
Задача:
дан DАG и две вершины s и e. Сколько различныхDirected путей существует из s в e?
Формула
dp[v] = Σ dp[u] для всех рёбер u → v
Базис:
dp[s] = 1 (один «путь нулевой длины» из s в s). Все остальные dp-значения инициализируются нулём.
Порядок обхода:
вершины в топологическом порядке (результат алгоритма Кана).
Псевдокод
topsort
← Kahn(G)
dp
[s] ← 1
for
v
in
topsort:
for
each u → v
in
edges:
dp[v] ← dp[v] + dp[u]
return
dp[e]
Сложность
O(V + E) — топсорт + один проход по рёбрам.
Расширение: самый длинный путь
Для задачи о критическом пути формула модифицируется:
dist[v] = max(dist[u] + w(u,v)) для всех u → v
Здесь w(u,v) — вес (длительность) ребра. Это классическая задача
CPM (Critical Path Method)
.
Пошаговый подсчёт путей A→G
Граф: A→B, A→C, B→D, B→E, C→E, C→F, D→G, E→G, F→G
Топсорт: A → B → C → E → F → D → G
Инициализация:
dp[A]=1, остальные dp=0
Шаг A:
ребро A→B (dp[B]+=dp[A]=1), A→C (dp[C]+=1)
→ dp: A=1, B=1, C=1, D=0, E=0, F=0, G=0
Шаг B:
ребро B→D (dp[D]+=dp[B]=1), B→E (dp[E]+=1)
→ dp: A=1, B=1, C=1, D=1, E=1, F=0, G=0
Шаг C:
ребро C→E (dp[E]+=dp[C]=1 → dp[E]=2), C→F (dp[F]+=1)
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=0
Шаг E:
ребро E→G (dp[G]+=dp[E]=2)
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=2
Шаг D:
ребро D→G (dp[G]+=dp[D]=1 → dp[G]=3)
→ dp: A=1, B=1, C=1, D=1, E=2, F=1, G=3
Шаг F:
ребро F→G (dp[G]+=dp[F]=1 → dp[G]=4)
Итого:
4 пути
из A в G!
Проверь в симуляторе: выбери старт=A, финиш=G, нажми «Считать».
def count_paths_dag(n, edges, start, end):
# edges = [(u, v), ...]
adj = [[] for _ in range(n)]
indeg = [0]*n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
# Кана: топологическая сортировка
q = [i for i in range(n) if indeg[i] == 0]
topo = []
while q:
v = q.pop(0)
topo.append(v)
for u in adj[v]:
indeg[u] -= 1
if indeg[u] == 0:
q.append(u)
# DP
dp = [0]*n
dp[start] = 1
for v in topo:
for u in adj[v]:
dp[u] += dp[v]
return dp[end]
# Пример:
edges = [(0,1),(0,2),(1,3),(1,4),(2,4),(2,5),(3,6),(4,6),(5,6)]
print(count_paths_dag(7, edges, 0, 6)) # 4
🔢
DP: подсчёт путей — анимация
03
Критический путь (CPM)
Метод критического пути (Critical Path Method, CPM)
— базовый инструмент управления проектами. Каждое задание — это ребро с весом (временем выполнения), каждая вершина — milestone (событие).
Что такое критический путь?
Критический путь — это
самый длинный путь
от начала до конца проекта. Он определяет минимально возможное время завершения проекта: если любое задание на критическом пути задерживается — задерживается весь проект.
Применение CPM
Строительство:
фундамент → стены → крыша → отделка. Критический путь = самый длительный участок.
Разработка ПО:
аналитика → проектирование → кодирование → тестирование.
Производство:
закупка материалов → сборка → покраска → упаковка.
Логистика:
маршрут с максимальной задержкой определяет общее время доставки.
Алгоритм
Найти топологический порядок вершин (алгоритм Кана).
Прямой проход: dist[v] = max(dist[u] + w(u,v)) для всех входящих рёбер u→v.
Обратный проход (необязательно): для каждого ребра на критическом пути最早/最迟 время совпадают.
Критический путь = множество рёбер, где dist[v] = dist[u] + w(u,v) и достижимость максимальна.
Важно
Критический путь не唯一的 — их может быть несколько. Все задания на критическом пути имеют
нулевой запас
(float = 0): их нельзя отложить без увеличения общего срока.
Пример
Задачи проекта:
A→B (3 дня), A→C (2 дня), B→D (4 дня), B→E (2 дня), C→E (3 дня), D→G (1 день), E→G (2 дня), F→G (1 день)
Критический путь:
A → B → D → G = 3+4+1 =
8 дней
(Путь A→B→E→G = 3+2+2 = 7 дней — не критический)
def cpm_critical_path(tasks):
# tasks = [{id, from, to, dur}, ...]
nodes = sorted(set(sum([[t['from'], t['to']] for t in tasks], [])))
adj = {n: [] for n in nodes}
indeg = {n: 0 for n in nodes}
for t in tasks:
adj[t['from']].append((t['to'], t['dur']))
indeg[t['to']] += 1
# Forward pass
early = {n: 0 for n in nodes}
q = [n for n in nodes if indeg[n] == 0]
order = []
while q:
v = q.pop(0)
order.append(v)
for to, w in adj[v]:
early[to] = max(early[to], early[v] + w)
indeg[to] -= 1
if indeg[to] == 0: q.append(to)
project_dur = early[order[-1]]
# Backward pass
late = {n: project_dur for n in nodes}
for v in reversed(order):
for to, w in adj[v]:
late[v] = min(late[v], late[to] - w)
# Float & critical path
critical = [t['id'] for t in tasks if late[t['from']] - early[t['from']] == 0]
return critical, project_dur
tasks = [
{'id':'A','from':'S','to':'A','dur':3},
{'id':'B','from':'S','to':'B','dur':2},
{'id':'C','from':'A','to':'C','dur':4},
{'id':'D','from':'A','to':'D','dur':2},
{'id':'E','from':'B','to':'D','dur':3},
{'id':'F','from':'C','to':'F','dur':1},
{'id':'G','from':'D','to':'G','dur':2},
{'id':'H','from':'E','to':'G','dur':1},
{'id':'I','from':'F','to':'I','dur':3},
{'id':'J','from':'G','to':'J','dur':2},
]
path, dur = cpm_critical_path(tasks)
print(f"Критический путь: {' → '.join(path)} ({dur} дней)")
⚡
CPM: пошаговый критический путь
04
Симулятор: подсчёт путей + критический путь
📊
DP: пути и критический путь
Старт
Финиш
05
Интерактив: CPM — Планировщик проекта
Смоделируй проект: задай длительности задач и узнай критический путь + резерв каждой задачи.
📋
CPM Project Scheduler
Зада