使用拓撲排序計算路徑

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）的路徑數的運行時間，這是迄今爲止最有效的解決方案。