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

Количество путей в ориентированном графе показывает, сколькими способами можно добраться из одной вершины в другую, двигаясь по стрелкам. Ответ зависит от того, разрешены ли повторные посещения вершин, задана ли длина и есть ли в графе циклы. Для ациклического графа все пути между двумя вершинами можно сосчитать динамическим программированием за один проход по рёбрам. В калькуляторе ниже исследуйте учебный граф: меняйте длину и сравнивайте число путей из А в Д.
Что именно считаем
Ориентированный граф состоит из вершин и направленных рёбер. Ребро разрешает переход из в , но обратного перехода само по себе не задаёт. Маршрут - последовательность вершин, в которой каждый соседний переход соответствует направленному ребру. Его длина равна числу рёбер, а не числу записанных вершин.
Будем называть простым путём маршрут без повторных вершин. Терминология в учебниках различается, поэтому в условии полезно явно указать, разрешены ли повторы. Здесь маршруты с повторами мы называем маршрутами, а слово «путь» используем для простого случая. В ориентированном ациклическом графе, или DAG, любой маршрут автоматически прост: повтор вершины означал бы ориентированный цикл. Подробнее устройство такого графа разобрано в статье про ориентированный ациклический граф.
Пустой маршрут из вершины в неё же имеет длину ноль. Обычно его учитывают как один способ остаться на месте. Если задача исключает его, это нужно оговорить: особенно заметна разница, когда начальная и конечная вершины совпадают. Далее рёбра между одной и той же парой вершин считаются различными вариантами перехода, если они явно заданы как параллельные; в нашем примере таких рёбер нет.
Пример: складываем пути к вершинам
Возьмём пять вершин А, Б, В, Г, Д и семь рёбер: А→Б, А→В, Б→В, Б→Г, В→Г, В→Д и Г→Д. Стрелки не позволяют вернуться к уже пройденной вершине. Запишем возле каждой вершины число способов попасть в неё из А. В начале у А стоит единица: это пустой маршрут.
До Б можно попасть одним способом. До В ведут прямое ребро из А и переход через Б, поэтому способов два. До Г можно добраться из Б или В: получаем . Наконец, в Д входят рёбра из В и Г, так что ответ равен . Все пять путей можно проверить вручную:
- А→В→Д;
- А→Б→В→Д;
- А→Б→Г→Д;
- А→В→Г→Д;
- А→Б→В→Г→Д.
Один путь содержит два ребра, три пути - три ребра и один - четыре. Калькулятор считает то же распределение: сумма столбцов равна пяти. Подсчёт отличается от поиска одного кратчайшего пути: последний отвечает на другой вопрос, как и алгоритм Дейкстры для взвешенного графа.

Динамическое программирование в DAG
Пусть - число путей из начальной вершины в . Положим , а остальные значения сначала сделаем нулями. Затем переберём вершины в топологическом порядке: каждое ребро направлено от более ранней вершины к более поздней. Для каждого ребра прибавим к .
Почему это работает? Каждый путь в , кроме пустого пути в самом источнике, имеет единственное последнее ребро. Если оно выходит из , то удаление этого ребра даёт путь в . И наоборот, к каждому пути в можно приписать ребро . Группы по последнему ребру не пересекаются, поэтому их размеры складываются. При параллельных рёбрах каждое ребро даёт свою группу, если маршруты по ним различают.
Порядок необходим: к моменту обработки все предшественники уже передали в неё свои вклады. Например, если обработать В до Б, путь А→Б→В ещё не будет учтён и итог окажется меньше правильного. Вершины, недостижимые из , сохраняют нулевое значение; обрабатывать их отдельно не требуется.
найти топологический порядок вершин
для каждой вершины v: d[v] = 0
d[s] = 1
для u в топологическом порядке:
для каждого ребра u → v:
d[v] = d[v] + d[u]
ответ: d[t]
Топологическую сортировку можно построить алгоритмом с входящими степенями либо с помощью обхода в глубину. Если сортировка не охватила все вершины, в графе есть цикл и приведённый алгоритм нельзя применять к нему как к DAG.
Сложность и большие ответы
При списках смежности топологическая сортировка и подсчёт выполняют операций, где - число вершин, - число рёбер. Массив чисел и рабочие структуры занимают дополнительной памяти, если сам граф уже хранится в списках смежности. Это оценка числа арифметических операций: сами числа путей могут иметь много разрядов, поэтому стоимость сложения больших целых тоже имеет значение.
Путей может быть экспоненциально много даже в DAG. Динамическое программирование не перечисляет каждый из них: оно хранит только количество для каждой вершины. Если условие просит вывести сами пути, времени потребуется как минимум столько, сколько занимает вывод. Если требуется остаток по модулю , можно брать его после каждого сложения; без такого условия заменять точный ответ остатком нельзя.
Пути заданной длины и матрица смежности
Для фиксированного числа рёбер удобно считать послойно. Обозначим через число маршрутов из в ровно за переходов. При единица стоит только у источника. На следующем шаге переносим каждое значение по всем исходящим рёбрам:
Здесь важно использовать отдельный новый массив: обновление старого массива на месте могло бы включить несколько переходов в один шаг. Метод работает и при циклах, потому что длина ограничена. За шагов он делает операций при очистке массива на каждом шаге и хранит два массива по чисел. В нашем DAG значения для Д при длинах от нуля до шести равны .
Ту же операцию записывают через матрицу смежности : элемент равен числу рёбер из в . Тогда элемент равен числу маршрутов длины из в , в том числе с повторениями. - единичная матрица, поэтому она учитывает пустой маршрут. Быстрое возведение матрицы в степень полезно при большом и сравнительно небольшом числе вершин, но стандартное умножение плотных матриц стоит арифметических операций и требует памяти.
Что меняется при циклах
Если из можно попасть на ориентированный цикл, а с него затем попасть в , число маршрутов без ограничения длины бесконечно: цикл можно пройти ноль, один или любое большее число раз. Цикл в другой части графа сам по себе бесконечность ответа не гарантирует. Нужно проверить обе достижимости, учитывая направления рёбер; для этого подойдёт, например, обход в ширину.
Простых путей в конечном графе всегда конечное число, поскольку ни одна вершина в таком пути не повторяется. Однако предыдущая формула для степеней матрицы считает и маршруты с повторами. Для подсчёта именно простых путей в общем графе можно использовать поиск с возвратом и отметками вершин текущего пути; в худшем случае он перебирает очень много вариантов. Нельзя просто пометить вершину посещённой навсегда: разные частичные пути могут приходить в неё с разными наборами уже использованных вершин.
Частые ошибки
- Игнорировать направление. Ребро А→Б не означает существования Б→А.
- Путать число путей с расстоянием. Длина и количество - разные характеристики; несколько путей могут иметь одинаковую длину.
- Обновлять DAG в произвольном порядке. Вклад должен прийти к вершине до того, как она передаст его дальше.
- Считать степень матрицы только простыми путями. При наличии циклов она включает повторные посещения.
- Забывать соглашение о нулевой длине и параллельных рёбрах. От него зависит ответ в пограничных случаях.
FAQ
Как найти число путей между двумя вершинами DAG? Задайте единицу источнику, пройдите вершины в топологическом порядке и передавайте количество по каждому исходящему ребру. Значение у цели и будет ответом.
Может ли ответ быть нулём? Да. Если цель недостижима из источника по направлению стрелок, подходящих путей нет. Для совпадающих источника и цели отдельно уточните, учитывается ли пустой путь.
Что считать при цикле и заданной длине? Для маршрутов с повторами примените послойную динамику или степень матрицы смежности. Для простых путей дополнительно нужно запрещать повторение вершин.
Коротко
В DAG число путей удобно накапливать по последним рёбрам в топологическом порядке. Для заданной длины подходят послойная динамика и степени матрицы смежности. При циклах сначала уточняйте, разрешены ли повторы: число неограниченных маршрутов может быть бесконечным, тогда как число простых путей конечно.
Читайте также

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

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

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

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

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

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