Задача о числе путей в ациклическом графе

Задача о числе путей в ациклическом графе - одна из классических задач на тему динамического программирования. В этой задаче нам дан ациклический граф [math]G[/math] и две вершины [math]s[/math] и [math]t[/math]. Необходимо посчитать количество путей из вершины [math]s[/math] в вершину [math]t[/math] по рёбрам графа [math]G[/math].

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее с помощью динамики.

Решение задачи

Перебор всех возможных путей

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

Функция [math]countPaths(s, t)[/math] принимает начальную вершину [math]s[/math] и конечную вершину [math]t[/math]. В глобальной переменной [math]answer[/math] содержится ответ.

answer = 0

count(v)
    if v == t
        answer += 1
    else
        for(всех [math]to[/math] смежных с [math]v[/math])
            count(to)

countPaths(s, t)
    answer = 0
    count(s)
    return answer

Время работы данного алгоритма в худшем случае [math]O(Ans)[/math], где [math]Ans[/math] - количество путей в графе.

Метод динамического программирования

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

Псевдокод

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

[math] count(v) = \left \{ \begin{array}{ll} d[v], & w[v]=true \\ \sum\limits_{c}count(c), & w[v]=false \end{array} \right. [/math]

count(v)
    if w[v]
        return d[v]
    else
        sum = 0
        for(всех [math]c[/math] смежных с [math]v[/math]):
            sum += count(c)
        d[v] = sum
        w[v] = true
        return sum

countPaths(s, t):
    d[s] = 1
    w[s] = true
    answer = count(t)
    return answer

Значение функции [math]count(v)[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\{e\ |\ end(e) = v\}[/math]. Всего таких ребер для всех вершин в графе [math]O(E)[/math], следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math], где [math]V[/math] - количество вершин графа, [math]E[/math] - количество ребер.

Пример работы

Рассмотрим пример работы алгоритма на следующем графе:

description