计算具有多个输入和一个输出的图中的所有路径

Question

我想从多个输入(x1，…)中计算有向无环图中的所有路径。， xn)到一个输出。图的深度与d和输入同时到达图的深度相同(形状类似于具有多个输入和一个输出的人工神经网络)。你能告诉我有没有算法可以计算这样的路径吗?

认为,

Answer 1

1)运行深度优先搜索，从输出开始，沿相反方向遍历每条边，找到可以到达输出的所有节点。

2)删除所有无法得到输出的节点。

3)在修改后的图上运行递归搜索，依次从每个输入节点开始，以找到通向输出的所有路径。

因为你已经移除所有的死角,这将产生所有路径尽可能快的输出,但你应该警告说,可能会有大量的不同路径,甚至小图表,图表梯子的形状和长度n可能2 ^ n路径——在每个阶段你可以选择是否去左边或右边的梯子,所以有2 ^(阶梯)不同路径。