簡單路徑

Question

我知道我自己，和其他許多人可能stuch這裏，

那麼，根據CLRS（3版，22.4.2），有一個O（n）的算法在有向無環圖中找到2個節點之間的所有簡單路徑。 我經歷了類似的問題，Number of paths between two nodes in a DAG和All the paths between 2 nodes in graph，但在兩種情況下，都沒有提到任何正確的解釋或僞代碼，或者如果是，我懷疑它是最有效的（O(n)）。

如果有人真的可以發佈一個確切的代碼或僞代碼來解決這個問題，因爲當我瀏覽所有上述鏈接時，我並沒有真正找到一個代表Tall的單個答案。

這將是更好的，如果該代碼還處理環狀圖表，即，如果在曲線圖中的週期，但如果兩個節點之間沒有路徑包含週期，路徑數應該是有限，否則無限。

Answer 1

Jeremiah Willcock的answer是正確的，但細節。這是DAG的線性時間算法。

for each node v, initialize num_paths[v] = 0 
let t be the destination and set num_paths[t] = 1 
for each node v in reverse topological order (sinks before sources): 
    for each successor w of v: 
     set num_paths[v] = num_paths[v] + num_paths[w] 
let s be the origin and return num_paths[s] 

我敢肯定，一般有向圖的問題是 #P-complete，但我無法找到除非cstheory的 unsourced question搜索的幾分鐘任何東西。

好的，這是一些僞代碼。我已經將前面的算法的內容與拓撲排序相結合，並添加了一些循環檢測邏輯。在s和t之間的循環的情況下，num_paths的值可能不準確，但取決於t是否可到達將爲零非零。一個循環中的每個節點都不會有in_cycle設置爲true，但是每當一個SCC根（在Tarjan的SCC算法中）就足以觸發提前退出，當且僅當s和t之間存在循環時。

REVISED ALGORITHM 

let the origin be s 
let the destination be t 
for each node v, initialize 
    color[v] = WHITE 
    num_paths[v] = 0 
    in_cycle[v] = FALSE 
num_paths[t] = 1 
let P be an empty stack 
push (ENTER, s) onto P 
while P is not empty: 
    pop (op, v) from P 
    if op == ENTER: 
     if color[v] == WHITE: 
      color[v] = GRAY 
      push (LEAVE, v) onto P 
      for each successor w of v: 
       push (ENTER, w) onto P 
     else if color[v] == GRAY: 
      in_cycle[v] = TRUE 
    else: # op == LEAVE 
     color[v] = BLACK 
     for each successor w of v: 
      set num_paths[v] = num_paths[v] + num_paths[w] 
     if num_paths[v] > 0 and in_cycle[v]: 
      return infinity 
return num_paths[s]