Топологическая сортировка, чтобы найти количество путей к t

Это можно сделать с помощью динамического программирования и топологической сортировки следующим образом:

Topological sort the vertices, let the ordered vertices be v1,v2,...,vn
create new array of size t, let it be arr
init: arr[t] = 1
for i from t-1 to 1 (descending, inclusive):
    arr[i] = 0  
    for each edge (v_i,v_j) such that i < j <= t:
         arr[i] += arr[j]

Когда вы закончите, для каждого i в [1,t] arr[i] указывает количество путей от vi до vt.

Теперь доказать приведенное выше утверждение легко (по сравнению с вашим алгоритмом, который я понятия не имею, верен ли он и как его доказать), это делается по индукции:

База: arr[t] == 1, и действительно, существует единственный путь от t до t, пустой.
Гипотеза: утверждение верно для каждого k в диапазоне m < k <= t
Доказательство: нам нужно доказать, что утверждение верно для m.
Давайте посмотрим на каждый край из vm: (v_m,v_i).
Таким образом, количество путей к vt, начиная с v_m, которые используют это ребро (v_m,v_i). равно arr[i] (предположение индукции). Суммирование всех возможных ребер от v_m дает нам общее количество путей от v_m до v_t - и это именно то, что делает алгоритм.
Таким образом, arr[m] = #paths from v_m to v_t

QED

Сложность по времени:
Первый шаг (топологическая сортировка) занимает O(V+E).
Цикл выполняет итерацию по всем ребрам один раз и по всем вершинам, так что это тоже O(V+E).
Это дает нам общую сложность O(V+E)