Топологическая сортировка (Кана) + динамическое программирование + критический путь.
Для ДАГ число путей считается за O(V+E) — топологически сортируем вершины, потом DP от старта. Тот же метод используется для критического пути в управлении проектами.
Топологическая сортировка — это линейная упорядоченная расстановка вершин Directed Acyclic Graph (DАГ) так, что для каждого ребра u→v вершина u стоит раньше v. Она является фундаментом для DP на графах.
Зачем нужен топсорт? Он гарантирует, что при обходе вершин в полученном порядке все предки каждой вершины уже обработаны — именно это нужно для корректного DP.
Задача: дан DАG и две вершины s и e. Сколько различныхDirected путей существует из s в e?
Базис: dp[s] = 1 (один «путь нулевой длины» из s в s). Все остальные dp-значения инициализируются нулём.
Порядок обхода: вершины в топологическом порядке (результат алгоритма Кана).
O(V + E) — топсорт + один проход по рёбрам.
Для задачи о критическом пути формула модифицируется:
Здесь w(u,v) — вес (длительность) ребра. Это классическая задача CPM (Critical Path Method).
Проверь в симуляторе: выбери старт=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
Метод критического пути (Critical Path Method, CPM) — базовый инструмент управления проектами. Каждое задание — это ребро с весом (временем выполнения), каждая вершина — milestone (событие).
Критический путь — это самый длинный путь от начала до конца проекта. Он определяет минимально возможное время завершения проекта: если любое задание на критическом пути задерживается — задерживается весь проект.
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} дней)")
Смоделируй проект: задай длительности задач и узнай критический путь + резерв каждой задачи.
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.