Информатика • 11 класс

Количество различных путей между вершинами ориентированного ациклического графа (Python)

Ациклический граф (DAG) – граф, в котором нет циклов (невозможно, выйдя из вершины, вернуться в неё, двигаясь по стрелкам).
Задача. Посчитать количество путей из вершины start в вершину end в ориентированном ациклическом графе (DAG).
- Алгоритм решения через динамическое программирование.
  - Инициализация. Создать массив dp, где dp [u] – количество путей из вершины u в end.
  - Базовый случай. dp [end] = 1.
  - Рекуррентность. Для всех вершин u (в обратном топологическом порядке): dp [u] = sum (dp [v] for v in neighbors [u])
    где существует ребро u → v.
  - Ответ: dp [start].
- Ключевые моменты:
  - граф без циклов → порядок обхода важен;
  - эффективно использовать топологическую сортировку;
  - сложность: O (N + M), где N – число вершин, M – рёбер.

Было полезно?