Как найти количество путей?

#    пункты назначения
#    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. Рекурсивно повторяем для каждого из этих узлов.

→ Ссылка