Решение: Количество путей в графе
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение по шагам
4 шагаГраф ориентированный и не содержит циклов, поэтому количество путей можно вычислять последовательно, начиная с города А.
Для каждой вершины число путей из А равно сумме чисел путей во всех вершинах, из которых в неё направлены дороги.
После последовательного подсчёта для всех промежуточных городов складываем числа путей, непосредственно ведущих в город Л.
Итоговое количество различных путей из А в Л равно 20.
Где здесь ошибаются
Не учитывать направление стрелок.
Считать города, а не различные маршруты.
Пропускать один из промежуточных вариантов пути.