1

我知道我自己和许多其他人可能都在这里，

好吧，根据CLRS(3 edition,22.4.2)，有一个 O(n) 算法可以在有向无环图中找到 2 个节点之间的所有简单路径。我经历了类似的问题，DAG 中两个节点之间的路径数和图中 2 个节点之间的所有路径，但是在这两种情况下，都没有提到正确的解释或伪代码，或者如果是，我怀疑这是最有效的（O(n)）。

如果有人真的可以发布一个确切的代码或伪代码来解决交易，因为当我浏览所有上述链接时，我并没有真正找到一个高大上的单一答案。

如果代码也处理循环图会更好，即如果图中存在循环，但如果两个节点之间的路径不包含循环，则路径的数量应该是有限的，否则是无限的。

4

1 回答 1

7

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设置为真，但每个 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]
于 2012-06-19T17:08:59.967 回答