可以使用动态编程和拓扑排序来完成此操作，如下所示：
Topological sort the vertices, let the ordered vertices be v1,v2,...,vncreate new array of size t, let it be arrinit: arr[t] = 1for 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
现在，证明上述主张很容易（与您的算法相比，我不知道它是否正确以及如何证明），这是通过归纳法完成的：
base
arr[t] == 1：，的确存在从t到t的唯一路径，即空路径。
假设 ：该索赔对
k范围内的每个索赔都是正确的
m < k <= t
证明 ：我们需要证明该索赔是正确的
m。
让我们看一下从每部边缘
vm：
(v_m,v_i)。
因此，
vt从
v_m该路径开始的路径数使用此edge
(v_m,v_i)。正是
arr[i]（归纳假设）。总结
v_m从
v_m到的所有可能边缘，可以得出从到的路径总数，
v_t而这正是算法的工作。
从而，
arr[m] = #paths from v_m to v_t
优质教育
时间复杂度：
第一步（拓扑排序）需要
O(V+E)。
循环将所有边缘迭代一次，并且对所有顶点迭代一次，所以也是
O(V+E)如此。
这使我们的整体复杂性
O(V+E)
