Simple Paths between 2 nodes

问题:

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

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.

回答1:

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]

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.

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]