2个节点之间的简单路径 [英] Simple Paths between 2 nodes

问题描述

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

I know that myself,and many others probably stuch here,

好吧，根据 CLRS（3版，22.4.2） >，有一个O（n）算法可用于查找有向无环图中2个节点之间的所有简单路径。
我遇到了类似的问题， DAG中两个节点之间的路径数和所有图中两个节点之间的路径，但是在两种情况下都没有提及适当的解释或伪代码，或者如果是，我怀疑它是否是最有效的（ O（n））。

Well,according to the CLRS(3 edition,22.4.2),there is a O(n) algorithm for finding all simple paths between 2 nodes in a directed acyclic graph. I went through similar questions,Number of paths between two nodes in a DAG and All the paths between 2 nodes in graph,but on both occasions,no proper explanation or pseudocode is mentioned,or if it is,i doubt that is it the most efficient one (O(n)).

如果有人真的可以发布一个确切的代码或伪代码来达成交易，因为我经过上述所有链接，我并没有真正找到一个代表塔尔的答案。

If someone could really post one exact code,or pseudocode,which settles the deal,because as i went through all those above links,i didnt really find 1 single answer which stands Tall.

如果代码还处理循环图（即如果图中有一个循环，但是如果两个节点之间没有路径包含循环，则路径数应为有限，否则无限。

It would be better if the code also handles cyclic graphs,i.e,IF there is a cycle in the graph,but If no path between two nodes contains the cycle,the number of paths SHOULD be FINITE,else INFINITE.

解决方案

耶利米·威尔科克的答案是正确的，但细节有所说明。这是DAG的线性时间算法。

Jeremiah Willcock's answer is correct but light on details. Here's the linear-time algorithm for DAGs.

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-完全，但是除了

I'm pretty sure the problem for general directed graphs is #P-complete, but I couldn't find anything in a couple minutes of searching except an unsourced question on cstheory.

好的，这是一些伪代码。我将先前算法的内容与拓扑排序进行了集成，并添加了一些周期检测逻辑。如果在 s 和 t 之间进行循环，则 num_paths 可能不准确，但将为零-非零，这取决于 t 是否可到达。并非周期中的每个节点都将 in_cycle 设置为true，但是每个SCC根（在Tarjan的SCC算法意义上）都将满足，如果和，则足以触发提前退出

Okay, here's some pseudocode. I've integrated the contents of the previous algorithm with the topological sort and added some cycle detection logic. In case of a cycle between s and t, the values of num_paths may be inaccurate but will be zero-nonzero depending on whether t is reachable. Not every node in a cycle will have in_cycle set to true, but every SCC root (in the sense of Tarjan's SCC algorithm) will, which suffices to trigger the early exit if and only if there is a cycle between s and 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]

这篇关于2个节点之间的简单路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！