Информатика · ОГЭ, ЕГЭ · 4 мин чтения
Как посчитать число путей по направленным дорогам?
Редакция Алгоса · Обновлено
Короткий ответ
В направленном графе без циклов подпиши старт числом 1, затем для каждой следующей вершины сложи количества путей во всех вершинах, из которых в неё входят стрелки. Полученная сумма и есть число путей до неё. Обрабатывай вершину после всех её предшественников. Мы считаем разные последовательности дорог, а не выбираем кратчайшую; длины дорог здесь не нужны.
Каждый путь входит последней стрелкой
Граф изображает объекты точками, или вершинами, а разрешённые переходы стрелками. Пусть заданы дороги A→B, A→C, B→C, B→D, C→D, C→E, D→E. Все они ведут вперёд в порядке A, B, C, D, E, поэтому вернуться циклом нельзя. Такой порядок позволяет закончить подсчёт для предыдущих вершин до перехода к следующим.
| Вершина | Откуда входят стрелки | Сумма | Путей из A |
|---|---|---|---|
| A | Старт | Начальное условие | 1 |
| B | A | 1 | 1 |
| C | A и B | 1 + 1 | 2 |
| D | B и C | 1 + 2 | 3 |
| E | C и D | 2 + 3 | 5 |
Почему пути складываются без повторного счёта?
Пути, приходящие по разным последним стрелкам, различаются хотя бы этим последним переходом. Один путь не может одновременно закончиться и стрелкой 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 три.
Циклы требуют другого условия задачи
Если разрешён цикл и можно повторять вершины, число маршрутов может быть бесконечным: петлю можно пройти сколько угодно раз. Приведённый алгоритм предназначен для графа без направленных циклов. Для недостижимой из старта вершины число путей равно нулю. Единица в старте означает один начальный пустой путь, а не дорогу из старта в себя.
- Проверь направления и отсутствие циклов.
- Подписывай вершину только после всех входящих предшественников.
Что запомнить
Число путей до вершины равно сумме вариантов входа в неё. Для этого нужен граф без направленных циклов.
Попробовать на Алгосе
Информатика для ОГЭ
В курсе можно связать расчёт с задачами по информатике и проверить способ на новых исходных данных.
Перейти к курсу Все курсы