简单路径

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]