algorithm - 使用拓扑排序计算路径

Question

我有一个 DAG，我需要计算从任何节点到另一个节点的所有路径，我研究了一点，我发现它可以用一些拓扑顺序来完成，但到目前为止，解决方案是不完整的或错误的。

那么正确的做法是怎样呢？

谢谢。

Answer 1

由于这是一个 DAG，您可以在 O(V+E) 时间内对节点进行拓扑排序。假设源顶点是 S。然后从 S 开始以深度优先的方式遍历节点。当我们处理节点 U 时，假设有一条边 U->V 那么 V 当然还没有被访问(为什么？因为它是一个有向无环图)所以你可以通过 d[U 中的节点 U 从 S 到达 V ] 方式，其中 d[U] 是从 S 到 U 的路径数。

所以从 S 到任何节点 V 的路径数，d[V] = d[x1]+d[x2]+d[x3]+ 。 . . +d[xy]，其中有 x1->V, x2->V, 之类的边。 . . xy->V

该算法将花费 O(V+E) 对图进行拓扑排序，然后计算最多 O(V*E ) 的路径数。您可以使用邻接表而不是邻接矩阵进一步减少其计算路径数 O(V+E) 的运行时间，这是迄今为止最有效的解决方案。