Problem Detail: What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information:
- Graph has 30,000 to 50,000 nodes
- Average number of edges per node ~ 10
- M=4, N=7
- Graph has cycles
Asked By : Andrew S.
Answered By : zvisofer
Assuming a directed graph. Paths of length $1$ are simply the edges. paths of length $i+1$: Unite on all nodes $v in V$ {concatenate all paths of length $i$ that end with $v$ with all paths of length $1$ that start with $v$}. repeat for $i=1$ to $7$. Note that this method avoids redundancies, so you don’t need to check for them.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21381
