2个节点之间的简单路径

Question

我知道我自己,还有很多人可能都在这里,

那么,根据CLRS(第3版,22.4.2),有一种O(n)算法用于在有向无环图中找到2个节点之间的所有简单路径.我经历了类似的问题去了,在DAG中两个节点之间的路径数和所有在图2级的节点之间的路径,但在这两个场合,没有适当的解释或伪代码中提到,或者如果它是的,我怀疑这是它最高效的一个(O(n)).

如果有人真的可以发布一个确切的代码,或者伪代码来解决这个问题,因为当我浏览了所有上述链接时,我并没有真正找到1个单独的答案.

它会更好,如果代码还可以处理循环图,即,如果有一个周期的图表,但如果没有路径两个节点之间包含了循环,路径的数量应该是有限的,否则无限的.

Answer 1

Jeremiah Willcock的答案是正确的,但细节很清楚.这是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 的无源问题外,我在几分钟的搜索中找不到任何东西.

好的,这是一些伪代码.我已经将前一算法的内容与拓扑排序集成在一起,并添加了一些循环检测逻辑.在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]