找到从有向图的初始层到达最后一层的方法总数的算法
algorithm to find the total number of ways to reach the last layer from the initial one of a directed graph
我想要一个算法来找到从最后一层和第一层只包含一个节点的有向图的初始层到达最后一层的方法总数。请建议我应该使用哪种算法。
如果从第一个节点到最后一个节点的路径有环路，则路径数无穷大
否则没有环，所以我们感兴趣的图的一部分是非环的（图中某处可能有环，但如果不在之间的路径上第一个和最后一个节点，无关紧要）。这就是为什么可以使用动态规划来计算路径数的原因：
基本情况：f(start node) = 1.
转换：f(node) = sum f(neighbor) for all neighbors of the node。我们可以正确计算出这个值，因为没有循环。
答案是f(last node).
我们可以显式使用拓扑排序，也可以编写带记忆的递归函数（在这两种情况下，时间和 space 复杂度都是线性的）。
我想要一个算法来找到从最后一层和第一层只包含一个节点的有向图的初始层到达最后一层的方法总数。请建议我应该使用哪种算法。
如果从第一个节点到最后一个节点的路径有环路，则路径数无穷大
否则没有环，所以我们感兴趣的图的一部分是非环的（图中某处可能有环，但如果不在之间的路径上第一个和最后一个节点，无关紧要）。这就是为什么可以使用动态规划来计算路径数的原因：
基本情况：
f(start node) = 1.转换：
f(node) = sum f(neighbor) for all neighbors of the node。我们可以正确计算出这个值，因为没有循环。答案是
f(last node).
我们可以显式使用拓扑排序，也可以编写带记忆的递归函数（在这两种情况下，时间和 space 复杂度都是线性的）。