Как найти количество путей?
# пункты назначения
# a, b, c, d, e, f, g, h, i, j, k, l
G = [ # пункты отправления
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0], # a
[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0], # b
[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], # c
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], # d
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0], # e
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0], # f
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], # g
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0], # h
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0], # i
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], # j
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], # k
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # l
]
Как при помощи алгоритма найти количество путей из точки x в точку y ?
1 - есть дорога, 0 - нет. Передвигаться можно только в одном направлении.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Если граф ациклический, то количество путей из узла X в узел Y есть сумма количества путей из Х во все узлы, из которых есть дуга в Y. Рекурсивно повторяем для каждого из этих узлов.