使用拓撲排序計算路徑

我有一個DAG，我需要計算從任何節點到另一個節點的所有路徑，我研究了一下，發現它可以用一些拓撲順序完成，但到目前爲止解決方案不完整或錯誤。使用拓撲排序計算路徑

那麼正確的方法怎麼做呢？

謝謝。

2013-07-15 bones.felipe

您可以使用遞歸來計算樹/ 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。

來源

2013-07-15 02:08:01 isaach1000

那麼這是我做的第一件事，但它似乎太慢了。這就是我研究和發現這種拓撲排序的原因。 –

爲什麼拓撲排序可以幫助您計算路徑？它旨在將非DAG轉換爲DAG，而不是簡化計數。 – isaach1000

因爲這個天真的遞歸在一些DAG上做了很多冗餘的工作。如果你記憶，記憶表最終按照拓撲順序構建。 –

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的所有路徑的數量。

來源

2013-07-15 02:29:15 Sayakiss

你在這裏記憶什麼？因爲它是一個DAG，所以i => j不會發生兩次:-) – Fallen

@Fallen避免重複計算.. – Sayakiss

對不起，忽略了自頂向下的方法:) – Fallen

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

來源

2013-07-15 02:41:26 Fallen

IT必須在相反的方向迭代拓撲排序列表？ –

@ bones.felipe：不，從根到葉。。。 – Fallen

但是，例如，如果我有這個拓撲列表：0-2-1-3其中除了0-> 1和2-> 3之外，它計數5否？ –

使用拓撲排序計算路徑

回答

相關問題