Информатика · объяснение и практика
Число путей в DAG: складываем способы, а не длины
Количество путей в ациклическом графе: сумма способов прийти к предшественникам, общий хвост и начальная единица в источнике.

В теме Графы и маршруты · Учебная карта
В маршруте Графы, разрезы и динамические запросы · 10 тем
Главная мысль
Для подсчёта направленных путей из заданного старта в DAG его вершины обрабатывают в топологическом порядке. В старте хранится один пустой способ, в остальных вершинах сначала ноль. Каждый переход добавляет число способов из предшественника к числу способов прийти в следующую вершину.
Считаем способы, а не посещения обхода
Одна вершина может быть посещена обходом один раз, хотя к ней ведут несколько различных путей. Поэтому обычная отметка «уже видели» не хранит нужное количество. Для каждой вершины отдельно накапливают, сколько различных последовательностей рёбер из заданного старта заканчивается именно в ней.
Начальная единица в источнике обозначает пустую последовательность до первого шага. Она позволяет каждому исходящему ребру получить один способ начала пути. У недостижимой вершины счётчик останется нулевым, и её исходящие рёбра не должны создавать новые пути из ничего. В этом разборе граф простой: параллельные рёбра отдельно не задаются.
Разбираем сеть с общим хвостом
Пусть рёбра равны S→A,S→B,A→B,A→C,B→C,B→T,C→T. В порядке S,A,B,C,T получаем: до S один способ, до A один, до B два — напрямую и через A. До C приходят один способ через A и два через B,всего три.
До T можно прийти последним ребром из B либо из C. Это две непересекающиеся группы путей по последнему ребру: первая содержит два способа, вторая три. Итого пять. Общие вершины и хвосты разных путей не делают сами последовательности одинаковыми, поэтому их нельзя просто объединить отметкой посещения.
Пример
Для указанного графа счётчики: S=1,A=1,B=2,C=3,T=5. Пути S→B→T и S→A→B→T различны, хотя используют общий хвост B→T.
Рекуррентное сложение группирует пути по последнему ребру. У двух перечисленных путей разные префиксы, поэтому оба должны учитываться.
Проверяем границы числового и графового предположения
Количество путей может быстро расти даже в небольшом DAG. Программа должна выбрать целые достаточной точности либо явно заявить, что считает остаток по модулю. Остаток не равен полному количеству: одинаковые остатки разных ответов не позволяют восстановить число путей без дополнительной информации.
При наличии направленного цикла топологического порядка нет. Если разрешить повторять вершины, число маршрутов в некоторых таких сетях становится бесконечным; если разрешать только простые пути, получается другая и более сложная задача. Поэтому проверка ацикличности входит в постановку, а не заменяется надеждой, что входной пример окажется удобным.
От чтения к действию
А теперь — вы
Частые вопросы
Почему в старте стоит 1,а не 0?
Единица обозначает один пустой путь до начала движения и запускает распространение способов по исходящим рёбрам.
Вершина посещена один раз — путь к ней только один?
Нет. Разные предшествующие последовательности могут закончиться в одной вершине, и все должны попасть в счётчик.
Углублённый разбор
Следующий простой путь через отклонение от уже найденного
Подсчёт путей не даёт их список в порядке стоимости. Алгоритм Йена перечисляет кратчайшие простые альтернативы через отклонения от уже принятого пути. Он сохраняет общую очередь кандидатов и запрещает возврат в корневой префикс, чтобы получать пути без повторных вершин.
Перед началом: Кратчайший путь; Приоритетная очередь.
Перечисляются разные пути, а не разные длины
Рассмотрим конечный ориентированный простой граф с неотрицательными весами. Путь прост, если не повторяет вершины. Требуется получить первые k различных последовательностей вершин в неубывающем порядке суммарной стоимости; несколько путей одной длины считаются разными ответами. Это отличается и от подсчёта всех путей в DAG, и от перечисления блужданий с повторными циклами.
Первый путь находится обычным алгоритмом кратчайшего пути. Для следующего рассматриваем каждую вершину последнего принятого пути как точку отклонения. Часть от s до неё фиксируем как root, оставшееся продолжение ищем заново как spur. Чтобы полный кандидат не повторил вершину префикса, все root-вершины, кроме точки отклонения, временно удаляем. Эта операция существенна и при нулевых весах.
Запрещаются продолжения всех уже принятых совпадающих корней
Для выбранного root проверяем все принятые пути, начинающиеся этим префиксом. У каждого временно запрещаем следующее ребро после root. Иначе поиск может снова вернуть уже выданную последовательность. На оставшемся графе находим кратчайший spur и склеиваем его с root без повторного включения общей вершины. Стоимость — сумма фиксированного префикса и нового продолжения.
Все полученные кандидаты помещаются в одну приоритетную очередь с устранением дубликатов. Выбираем из неё минимальный, добавляем в принятые и повторяем генерацию отклонений для него. Очередь нельзя очищать после очередного принятия: более старый кандидат может оказаться дешевле всех новых. При равных стоимостях допустим любой согласованный порядок; если нужен лексикографический, его задают отдельно.
Отклонение покрывает ещё не выданные альтернативы
У любого другого пути найдётся первый участок, где он расходится с уже рассмотренным корнем. Запрет использованных продолжений оставляет это направление, а кратчайший spur создаёт кандидата не дороже соответствующего продолжения. Общая очередь сохраняет лучшие ещё не выданные отклонения, что обеспечивает неубывание результатов. Для маленького графа независимый полный DFS всех простых путей удобен для проверки рангов; на больших графах их число может быть экспоненциальным, поэтому перечисление ограничивают нужным k.
Старые кандидаты нужны для третьего ответа
Условие. Дуги: s→a=1,s→b=3,a→b=1,a→c=4,a→t=8,b→c=1,b→t=4,c→t=1. Найдите длины первых трёх различных простых s–t путей и объясните сохранение очереди.
- Первый путь P₁=s–a–b–c–t имеет длину 4. Его отклонение в s даёт s–b–c–t длины 5.
- Отклонение в a после запрета a→b даёт s–a–c–t длины 6. Отклонение в b после запрета b→c даёт s–a–b–t тоже длины 6. Оба кандидата остаются в общей очереди.
- Из очереди принимаем P₂=s–b–c–t длины 5. Для его корня s теперь запрещены оба исходных продолжения s→a и s→b. Для корня s–b отклонение даёт s–b–t длины 7.
- В очереди всё ещё лежат два старых пути длины 6, поэтому третья длина равна 6, а не7. Какой из двух равных путей станет третьим, зависит от соглашения о равенстве ключей.
Ответ. Первые три длины равны 4,5,6; третий путь можно выбрать s–a–b–t или s–a–c–t.
Проверка. Независимый полный перебор находит 6 простых путей со стоимостями 4,5,6,6,7,9. Ни один не повторяет вершины; очередь отклонений согласуется с этим порядком и сохраняет обе равные альтернативы.
Где легко ошибиться. Не очищайте общую очередь и не запрещайте продолжение лишь последнего пути с данным root. Первая ошибка теряет дешёвые старые кандидаты, вторая возвращает дубликаты.
Проверьте понимание
Вопросы к этой главе
Почему в примере граф ациклический, хотя метод умеет циклы?
DAG позволяет полностью перечислить альтернативы для короткой независимой проверки. Запрет root-вершин становится особенно заметен на циклическом графе, но остаётся частью общего метода и не меняет правильный результат на DAG.
Как отличить третий путь от третьей различной стоимости?
Здесь считаются последовательности вершин. Два пути длины 6 занимают два места в выдаче. Если нужны разные численные стоимости, потребуется отдельная фильтрация, и это уже другая постановка перечисления.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- NetworkX: shortest_simple_paths, official documentation/source
Прочитаны оригинальная реализация Yen, listA/listB, исключение root-вершин и продолжений всех принятых путей, PathBuffer с удалением дубликатов. Документация определяет простой путь без повторных вершин и запрещает отрицательные веса. Собственный DAG и остаточная очередь кандидатов не из примеров проекта.
Ранг и разранжирование путей DAG по числам продолжений
Числа продолжений из вершин DAG позволяют адресовать отдельный путь по его порядковому номеру. Лексикографическое ранжирование складывает размеры пропущенных ветвей, а обратная операция выбирает нужный интервал. Перечислять все предыдущие пути для этого не требуется.
Перед началом: Обратная топологическая динамика; Лексикографический порядок и нумерация с нуля.
Суффиксный счётчик задаёт размер каждой ветви
Зафиксируем старт s, целевую вершину t без исходящих дуг и порядок соседей. Граф простой ориентированный и ациклический; пути различаются последовательностями вершин. Положим C(t)=1 — один пустой хвост. Для остальных C(v)=Σ_(v→u)C(u), вычисляя значения в обратном топологическом порядке.
Если вершина не достигает t, её счётчик равен нулю. Каждый исходящий сосед задаёт отдельную группу путей, поскольку первая следующая вершина различается. Размер такой группы равен C(u). Поэтому отсортированные соседи разбивают номера от нуля до C(v)−1 на последовательные непересекающиеся интервалы.
Разранжирование последовательно сужает номер
Для допустимого k с 0≤k<C(s) просматриваем соседей в порядке. Если k≥C(u), пропускаем всю ветвь и вычитаем её размер. Иначе выбираем u и продолжаем с тем же локальным k. Достижение t завершает путь. Нулевые ветви не выбираются и не меняют номер.
Обратное ранжирование для готового пути суммирует размеры всех более ранних соседних ветвей в каждой посещённой вершине. Затем переходит по фактическому ребру пути. Эти операции обратны благодаря разбиению на интервалы. Числа C должны быть точными целыми: остатки по модулю не сохраняют сравнения k с размерами блоков.
Порядок путей требует договорённости о различимости
При параллельных дугах одинаковые последовательности вершин могут соответствовать разным последовательностям рёбер. Тогда нужны отдельные идентификаторы дуг и порядок по ним; молчаливое суммирование повторов изменит пространство ранжирования. В выбранном простом графе такой неоднозначности нет.
Число путей может быть экспоненциальным, но сами счётчики имеют конечную двоичную длину. Предварительная динамика обслуживает много запросов ранга. Стоимость вывода пути всё равно не меньше его длины, а просмотр списков соседей зависит от представления интервалов. Без дополнительного индекса не следует обещать постоянное время выбора ветви произвольной степени.
Пятый путь без перечисления четырёх предыдущих
Условие. Списки соседей: s:[p,q], p:[r,u], q:[t,u], r:[t], u:[r,t], t:[]. Порядок уже указан. Найдите путь с нулевым рангом 4 и ранг пути s→p→u→t.
- Обратная динамика даёт C(t)=1,C(r)=1,C(u)=2,C(p)=3,C(q)=3,C(s)=6.
- Для k=4 в s пропускаем три пути ветви p. Выбираем q с локальным номером один.
- В q сначала идёт t, его блок содержит один путь. Пропускаем его, получаем ноль и выбираем u. В u нулевой номер относится к r, затем единственное продолжение ведёт в t.
- Получен путь s→q→u→r→t. Его глобальный ранг равен 3+1+0+0=4.
- Для s→p→u→t сначала не пропускаем ветвь p. В p пропускаем r размером один, а в u пропускаем r размером один. Итоговый ранг равен двум.
Ответ. Ранг 4 задаёт s→q→u→r→t. Путь s→p→u→t имеет ранг 2; всего допустимых путей шесть.
Проверка. Полное независимое перечисление только этого малого DAG даёт шесть лексикографических путей и подтверждает обе операции. Проверка rank(unrank(k))=k выполнена для всех шести номеров.
Где легко ошибиться. Не используйте число путей из старта как размер будущей ветви. Для выбора следующего шага нужен суффиксный счётчик путей из соседа до фиксированного t.
Проверьте понимание
Вопросы к этой главе
Почему C(t)=1, хотя в t нет исходящей дуги?
Путь уже завершён, и существует один способ ничего больше не дописывать. Нулевая база уничтожила бы все счётчики предшественников.
Можно ли ранжировать по остаткам счётчиков?
Нет. Сравнение номера с размером ветви требует полного целого значения. Даже правильный остаток не показывает, сколько путей нужно пропустить.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Boost Graph Library 1.82: topological DAG path processing
Прочитано описание обработки путей по топологическому порядку DAG. Источник решает взвешенную задачу, а суффиксные количества, интервалы рангов и их обратимость выведены здесь отдельно. Версия документации закреплена; её API не объявляется инструментом ранжирования.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Длиннейший путь в DAG: когда работает топологический порядок
Максимальная сумма весов в DAG: фиксированный старт, недостижимые вершины, отрицательные рёбра и обновления в топологическом порядке.
Открыть темуСильные компоненты: какие вершины взаимно достижимы
Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.
Открыть тему