All paths of less than a given length in a directed graph between couple of nodes

Problem Detail: 

Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, due to the possibles cycles.

This question is slightly different, or at least I think.

INPUT: Be G a directed graph. G can have cycles and also selfconnected nodes. Let A(G) be the adjacency matrix of G (with a 1 in G_i,j if there's a link going from i to j and a 0 otherwise). Define T and B two subset of nodes of G, possibly with void intersection.

OUTCOME: A list of all paths of length at most k going from one node in T to one node in B. Paths can contain multiple time the same edges, as long as they go from the source node to the target node in strictly less than k+1 steps.

QUESTION: I would like to know which algorithm perform best in this task. I'm trying to develop a possible answer based on the fact that the n-th power of the adjacency matrix, if computed symbolically (with a different variable for each entry instead of a 1), keep traks of all this paths (and it reduces to the counting of paths if computed numerically with 1 in the entries). But I really don't know if this is the fastest way of doing the task (probably not).

CAVEAT: I'm not asking for the counting problem, nor for the shortest paths, the length of a path is defined as the number of edges used (counting the repetition). I'm using R, but if you prefer think about it in any other language! I'm really sorry if the question was already posed and solved. Thank you for the kind help!

additional info: I tried a matrix power series approach (A^3 gives all the 3 long path, ...) and dfs / bfs. I think the latter two are far from optimality as they don' take into account that I'm working on sets of sources and targets, and hence do a lot of redundant work...

Asked By : gvdr

Answered By : Kaveh

If I am not missing something about your question, you can apply the standard trick for reducing the question about multiple sources and destinations to the case of single source and single destination:

1. Add two new nodes $s$ and $t$,
2. Connect $s$ to all sources,
3. Connect all destinations to $t$.

After this reduction we are in the standard question setting with two extra vertices $s$ and $t$ and we want to find walks from $s$ to $t$ of length at most $k+2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10949