我想计算有向无环图中从多个输入（x1, .., xn）到一个输出的所有路径。该图具有相同的深度d，并且输入同时进入图中（形状类似于具有多个输入和一个输出的神经网络）。请问是否有可以计算此类路径的算法？

此致，

回答：

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

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

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

由于你已经移除了所有死胡同，这应该能以最快的速度生成所有路径，但你应该注意，即使是小图，也可能有非常多的不同路径——一个形状像梯子的图，长度为n，可能有大约2^n条路径——在每个梯级上，你可以选择走梯子的左侧还是右侧，因此有2^(梯级数量)条不同的路径。