Как считать пути и находить оптимальный маршрут в ациклическом графе?

Ориентированный ациклический граф не содержит направленного цикла, поэтому его вершины можно упорядочить так, чтобы каждое ребро шло слева направо. Топологический порядок превращает задачи о путях в последовательное вычисление: к моменту обработки вершины сведения обо всех её предшественниках уже готовы.

Топологический порядок

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

Число путей

Пусть ways[start] = 1, а остальные значения равны нулю. При обработке вершины v её число путей добавляют каждому соседу u по ребру v → u. Каждому пути в u однозначно соответствует последний переход из некоторого предшественника, поэтому суммы не пропускают и не дублируют маршруты.

Минимальный вес

Вместо количества хранят лучшее расстояние. Начальная вершина получает ноль, недостижимые — бесконечность. Для каждого ребра проверяют улучшение dist[u] через dist[v] + weight. В DAG допустимы даже отрицательные веса: цикл, который бесконечно уменьшал бы стоимость, отсутствует.

Восстановление ответа

Если релаксация улучшила значение, сохраняют predecessor[u] = v. После вычисления путь восстанавливают от цели к старту и разворачивают. Если расстояние осталось бесконечным, маршрута нет; массив предков нельзя читать как готовый путь.

Проверка модели

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

Динамика по топологическому порядку

В DAG каждое ребро направлено от более ранней вершины топологического порядка к более поздней. Поэтому к моменту обработки вершины уже известны результаты всех предшественников. Для числа путей значение источника равно единице, остальные начинают с нуля; вклад dp[v] передаётся по каждому исходящему ребру.

def count_paths_dag(graph: list[list[int]], order: list[int], start: int) -> list[int]:
    paths = [0] * len(graph)
    paths[start] = 1
    for vertex in order:
        for neighbour in graph[vertex]:
            paths[neighbour] += paths[vertex]
    return paths

graph = [[1, 2], [3], [3], []]
assert count_paths_dag(graph, [0, 1, 2, 3], 0)[3] == 2

Переданный order является предусловием функции. В производственном решении его получают алгоритмом Кана или DFS и проверяют, что обработаны все вершины; иначе граф содержит цикл.

Практика: оптимальный маршрут с восстановлением

Добавьте веса рёбер и вычислите минимальную стоимость от источника до каждой вершины в топологическом порядке. Для недостижимых вершин используйте бесконечность, при улучшении сохраняйте предка. Восстановите маршрут до стока и проверьте его сумму независимо. Затем добавьте ребро, создающее цикл: покажите, как алгоритм топологической сортировки обнаружит нарушение предпосылки, вместо выдачи правдоподобного неверного ответа.