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 Gi,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...