拓扑排序以查找到t的路径数

拓扑排序以查找到t的路径数

可以使用动态编程和拓扑排序来完成此 *** 作，如下所示：

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)