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

Задача о числе путей в ациклическом графе - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.

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

• Постановка задачи

Дан ациклический граф [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], причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.

count(v):
    if v == t:
        ans += 1
    else:
        for(child : v):
            count(child)

Время работы данного алгоритма [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]v[/math]. Мы свели нашу задачу к более мелким подзадачам, причем мы также знаем, что [math]P(s) = 1[/math]. Это позволяет решить задачу методом динамического программирования.

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

Асимптотика алгоритма [math]O(V + E)[/math], где [math]V[/math] - количество вершин графа, [math]E[/math] - количество вершин. Значения функции [math]P(v)[/math] вычисляются один раз для кажой вершины, и каждый раз просматриваются ребра [math]P(v)[/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]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_{parent}count(parent), & w[v]=false \end{array} \right. [/math]

count(v):
    if w[v]:
        return d[v]
    else:
        sum = 0
        for(parent : v):
            sum += count(parent)
        d[v] = sum
        w[v] = true
        return sum

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