EssayAI
Блог
Блог
Естественные науки

Количество путей в ориентированном графе

8 ноября 2026Время чтения: 8 минут
#ориентированный граф#количество путей#динамическое программирование#матрица смежности#алгоритмы
Количество путей в ориентированном графе

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

Что именно считаем

Ориентированный граф состоит из вершин и направленных рёбер. Ребро u→vu\to v разрешает переход из uu в vv, но обратного перехода само по себе не задаёт. Маршрут - последовательность вершин, в которой каждый соседний переход соответствует направленному ребру. Его длина равна числу рёбер, а не числу записанных вершин.

Будем называть простым путём маршрут без повторных вершин. Терминология в учебниках различается, поэтому в условии полезно явно указать, разрешены ли повторы. Здесь маршруты с повторами мы называем маршрутами, а слово «путь» используем для простого случая. В ориентированном ациклическом графе, или DAG, любой маршрут автоматически прост: повтор вершины означал бы ориентированный цикл. Подробнее устройство такого графа разобрано в статье про ориентированный ациклический граф.

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

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

Возьмём пять вершин А, Б, В, Г, Д и семь рёбер: А→Б, А→В, Б→В, Б→Г, В→Г, В→Д и Г→Д. Стрелки не позволяют вернуться к уже пройденной вершине. Запишем возле каждой вершины число способов попасть в неё из А. В начале у А стоит единица: это пустой маршрут.

Золотая стрелка показывает ребро, по которому переносится вклад; числа путей накапливаются до 5 в Д, затем шаги прокручиваются назад.

До Б можно попасть одним способом. До В ведут прямое ребро из А и переход через Б, поэтому способов два. До Г можно добраться из Б или В: получаем 1+2=31+2=3. Наконец, в Д входят рёбра из В и Г, так что ответ равен 2+3=52+3=5. Все пять путей можно проверить вручную:

  1. А→В→Д;
  2. А→Б→В→Д;
  3. А→Б→Г→Д;
  4. А→В→Г→Д;
  5. А→Б→В→Г→Д.

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

В графе числа путей из А до вершин равны 1, 1, 2, 3 и 5; в Д входят 2 пути через В и 3 через Г
В графе числа путей из А до вершин равны 1, 1, 2, 3 и 5; в Д входят 2 пути через В и 3 через Г

Динамическое программирование в DAG

Пусть d[v]d[v] - число путей из начальной вершины ss в vv. Положим d[s]=1d[s]=1, а остальные значения сначала сделаем нулями. Затем переберём вершины в топологическом порядке: каждое ребро направлено от более ранней вершины к более поздней. Для каждого ребра u→vu\to v прибавим d[u]d[u] к d[v]d[v].

d[v]+=d[u].d[v] \mathrel{+}= d[u].

Почему это работает? Каждый путь в vv, кроме пустого пути в самом источнике, имеет единственное последнее ребро. Если оно выходит из uu, то удаление этого ребра даёт путь в uu. И наоборот, к каждому пути в uu можно приписать ребро u→vu\to v. Группы по последнему ребру не пересекаются, поэтому их размеры складываются. При параллельных рёбрах каждое ребро даёт свою группу, если маршруты по ним различают.

Порядок необходим: к моменту обработки uu все предшественники уже передали в неё свои вклады. Например, если обработать В до Б, путь А→Б→В ещё не будет учтён и итог окажется меньше правильного. Вершины, недостижимые из ss, сохраняют нулевое значение; обрабатывать их отдельно не требуется.

найти топологический порядок вершин
для каждой вершины v: d[v] = 0
d[s] = 1
для u в топологическом порядке:
    для каждого ребра u → v:
        d[v] = d[v] + d[u]
ответ: d[t]

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

Сложность и большие ответы

При списках смежности топологическая сортировка и подсчёт выполняют O(V+E)O(V+E) операций, где VV - число вершин, EE - число рёбер. Массив чисел и рабочие структуры занимают O(V)O(V) дополнительной памяти, если сам граф уже хранится в списках смежности. Это оценка числа арифметических операций: сами числа путей могут иметь много разрядов, поэтому стоимость сложения больших целых тоже имеет значение.

Путей может быть экспоненциально много даже в DAG. Динамическое программирование не перечисляет каждый из них: оно хранит только количество для каждой вершины. Если условие просит вывести сами пути, времени потребуется как минимум столько, сколько занимает вывод. Если требуется остаток по модулю MM, можно брать его после каждого сложения; без такого условия заменять точный ответ остатком нельзя.

Пути заданной длины и матрица смежности

Для фиксированного числа рёбер удобно считать послойно. Обозначим через fk[v]f_k[v] число маршрутов из ss в vv ровно за kk переходов. При k=0k=0 единица стоит только у источника. На следующем шаге переносим каждое значение по всем исходящим рёбрам:

fk+1[v]=∑u→vfk[u].f_{k+1}[v]=\sum_{u\to v} f_k[u].

Здесь важно использовать отдельный новый массив: обновление старого массива на месте могло бы включить несколько переходов в один шаг. Метод работает и при циклах, потому что длина ограничена. За KK шагов он делает O(K(V+E))O(K(V+E)) операций при очистке массива на каждом шаге и хранит два массива по VV чисел. В нашем DAG значения для Д при длинах от нуля до шести равны 0,0,1,3,1,0,00, 0, 1, 3, 1, 0, 0.

Ту же операцию записывают через матрицу смежности AA: элемент AuvA_{uv} равен числу рёбер из uu в vv. Тогда элемент (Ak)st(A^k)_{st} равен числу маршрутов длины kk из ss в tt, в том числе с повторениями. A0A^0 - единичная матрица, поэтому она учитывает пустой маршрут. Быстрое возведение матрицы в степень полезно при большом kk и сравнительно небольшом числе вершин, но стандартное умножение плотных матриц стоит O(V3log⁡k)O(V^3\log k) арифметических операций и требует O(V2)O(V^2) памяти.

Что меняется при циклах

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

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

Частые ошибки

  • Игнорировать направление. Ребро А→Б не означает существования Б→А.
  • Путать число путей с расстоянием. Длина и количество - разные характеристики; несколько путей могут иметь одинаковую длину.
  • Обновлять DAG в произвольном порядке. Вклад должен прийти к вершине до того, как она передаст его дальше.
  • Считать степень матрицы только простыми путями. При наличии циклов она включает повторные посещения.
  • Забывать соглашение о нулевой длине и параллельных рёбрах. От него зависит ответ в пограничных случаях.

FAQ

Как найти число путей между двумя вершинами DAG? Задайте единицу источнику, пройдите вершины в топологическом порядке и передавайте количество по каждому исходящему ребру. Значение у цели и будет ответом.

Может ли ответ быть нулём? Да. Если цель недостижима из источника по направлению стрелок, подходящих путей нет. Для совпадающих источника и цели отдельно уточните, учитывается ли пустой путь.

Что считать при цикле и заданной длине? Для маршрутов с повторами примените послойную динамику или степень матрицы смежности. Для простых путей дополнительно нужно запрещать повторение вершин.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

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

8 ноября 20269 минут
Наибольшая общая подпоследовательность: алгоритм и пример

Наибольшая общая подпоследовательность: алгоритм и пример

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

8 ноября 20269 минут
Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые без учёта порядка: примеры, отличие от упорядоченных сумм, рекуррентная формула и алгоритм динамического программирования.

8 ноября 20269 минут
Задача о рюкзаке: динамическое программирование

Задача о рюкзаке: динамическое программирование

Разбор задачи о рюкзаке (0/1 Knapsack) методом ДП: таблица dp[i][w], рекуррентный переход, traceback-восстановление набора. Пошаговые примеры и анализ сложности O(n*W).

17 июня 20267 минут
Алгоритм Кадане: максимальная сумма подмассива

Алгоритм Кадане: максимальная сумма подмассива

Алгоритм Кадане за линейное время находит подмассив с наибольшей суммой. Разбираем идею динамического программирования, ловушку отрицательных чисел и реализацию.

6 февраля 202610 минут
Алгоритм Беллмана-Форда: пути с отрицательными весами

Алгоритм Беллмана-Форда: пути с отрицательными весами

Разбираем алгоритм Беллмана-Форда: как искать кратчайшие пути в графе с отрицательными рёбрами, ловить отрицательные циклы и чем он отличается от Дейкстры.

18 января 202610 минут