1

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.

Community
  • 1
  • 1
Spandan Pathak
  • 37
  • 1
  • 6

1 Answers1

7

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]
Community
  • 1
  • 1
rich
  • 136
  • 2
  • ,Could you please suggest as on how to modify it to detect cycle,cuz in that case,numpaths would be INFINITE? – Spandan Pathak Jun 19 '12 at 17:22
  • rich,thanks a lot.It works like a dream.But it doesnt handle the case when there is a cycle in graph(yeah i admit i asked bout DAG),but still if could suggest modification.! – Spandan Pathak Jun 19 '12 at 19:56
  • You can detect cycles while determining the topological order - the DFS will double back on a gray node. – rich Jun 19 '12 at 20:29
  • But that would find every cycle present in graph,even if the cycle is not NOT reachable from both,Source and sink. – Spandan Pathak Jun 20 '12 at 06:42
  • BTW, I've kept WHITE/GRAY/BLACK and in_cycle separate for pedagogical reasons, but an efficient implementation could use four combined states WHITE/GRAYNOCYCLE/GRAYCYCLE/BLACK. – rich Jun 20 '12 at 14:22