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) 路径数的运行时间，这是迄今为止最有效的解决方案。

Answer 2

您可以使用递归来计算树/DAG 中的所有路径。这是伪代码：

function numPaths(node1, node2):
    // base case, one path from node to itself
    if (node1 == node2): return 1

    totalPaths = 0
    for edge in node1.edges:
        nextNode = edge.destinationNode
        totalPaths += numPaths(nextNode, node2)

    return totalPaths

编辑： 解决这个问题的一个很好的动态方法是Floyd-Warshall algorithm。

Answer 3

Assume G(V,E)
Let d[i][j] = the number of all the paths from i to j
Then d[i][j]= sigma d[next][j] for all (i,next) in E

好像太慢了？好的。记住它（有些人称之为动态编程）。像这样

memset(d,-1,sizeof(d))// set all of elements of array d to -1 at the very beginning
saya(int i,int j)
{
    if (d[i][j]!=-1) return d[i][j];//d[i][j] has been calculated
    if (i==j) return d[i][j]=1;//trivival cases
    d[i][j]=0;
    for e in i.edges
        d[i][j]+=saya(e.next,j);
    return d[i][j];
}

现在 saya(i,j) 将返回从 i 到 j 的所有路径的数量。