使用拓扑排序计算路径

Question

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

那么正确的方法怎么做呢？

谢谢。

Answer 1

您可以使用递归来计算树/ 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 2

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的所有路径的数量。

Answer 3

由于这是一个DAG，您可以在O（V + E）时间内对拓扑进行拓扑排序。假设源顶点为S.然后从S开始以深度第一方式遍历节点。当我们处理节点U时，假设有一个边U-> V，那么V当然还没有被访问（为什么？因为它是一个有向无环图）所以你可以通过节点U在S到V达到d [U ]方式，其中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）的路径数的运行时间，这是迄今为止最有效的解决方案。