Изменения

Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <tex>s</tex>. При каждом посещении вершины <tex>v</tex> проверим, не является ли она искомой вершиной <tex>t</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от для всех вершин, ребра в которые выходят есть ребро из <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.

Пусть <tex>P(v)</tex> - количество путей от вершины <tex> s </tex> до вершины <tex>v</tex>.Можно заметить, что Тогда <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что <tex>\exists</tex> есть ребро из <tex>c</tex> в <tex>v</tex>. Мы свели нашу задачу к более мелким меньшим подзадачам, причем мы также знаем, что <tex>P(s) = 1</tex>. Это позволяет решить задачу методом динамического программирования.

Пусть <tex>s</tex> - стартовая вершина, а <tex>t</tex> - конечная, для нее и посчитаем ответ. Будем поддерживать массив <tex>d</tex>, где <tex>d[v]</tex> - количество путей из вершины <tex> s </tex> до вершины <tex>v</tex> и массив <tex>w</tex>, где <tex>w[v] = true</tex>, если ответ для вершины <tex>v</tex> уже посчитан, и <tex>w[v] = false</tex> в противном случае. Изначально <tex>w[i] = false</tex> для всех вершин <tex>i</tex>, кроме <tex>s</tex>, а <tex>d[s] = 1</tex>. Функция <tex>count(v)</tex> будет возвращать ответ для вершины <tex>v</tex>. Удобнее всего это реализовать в виде рекурсивной функции с помощью ленивой рекурсии, тогда запоминанием. В этом случае значения массива <tex>d</tex> будут вычисляться по мере необходимости, а засчет запоминания результатов они и не будут считаться лишний раз: