Информатика · ОГЭ, ЕГЭ · 4 мин чтения

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

Редакция Алгоса · Обновлено

Короткий ответ

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

Каждый путь входит последней стрелкой

Граф изображает объекты точками, или вершинами, а разрешённые переходы стрелками. Пусть заданы дороги A→B, A→C, B→C, B→D, C→D, C→E, D→E. Все они ведут вперёд в порядке A, B, C, D, E, поэтому вернуться циклом нельзя. Такой порядок позволяет закончить подсчёт для предыдущих вершин до перехода к следующим.

Суммируем варианты входа в каждую вершину
ВершинаОткуда входят стрелкиСуммаПутей из A
AСтартНачальное условие1
BA11
CA и B1 + 12
DB и C1 + 23
EC и D2 + 35
Почему пути складываются без повторного счёта?

Пути, приходящие по разным последним стрелкам, различаются хотя бы этим последним переходом. Один путь не может одновременно закончиться и стрелкой C→E, и стрелкой D→E. Поэтому группы не пересекаются, а их количества можно сложить. Саму входящую стрелку дополнительно прибавлять не нужно.

Сверь короткий граф прямым перечислением

По таблице из A в E ведут пять путей. На маленькой схеме их полезно выписать независимо, чтобы проверить стрелки. Самый короткий по количеству переходов путь не отменяет остальных: задача спрашивает число допустимых последовательностей. Если отдельная дорога не нарисована и не перечислена в условии, добавить её по сходству картинки нельзя.

Все пять вариантов

A→C→E; A→C→D→E; A→B→C→E; A→B→C→D→E; A→B→D→E. Последние стрелки делят их на две группы: через C напрямую приходят два пути, через D три.

Циклы требуют другого условия задачи

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

  1. Проверь направления и отсутствие циклов.
  2. Подписывай вершину только после всех входящих предшественников.

Что запомнить

Число путей до вершины равно сумме вариантов входа в неё. Для этого нужен граф без направленных циклов.

Попробовать на Алгосе

Информатика для ОГЭ

В курсе можно связать расчёт с задачами по информатике и проверить способ на новых исходных данных.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы