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
  • 8
    $\begingroup$ Brute force enumeration requires O(1) time, which is clearly optimal. $\endgroup$ – JeffE Feb 1 '14 at 21:08

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.

  • 3
    $\begingroup$ I'm not one of the down-voters, but another guess might be that a strict interpretation of your solution counts walks, not (simple) paths. $\endgroup$ – Yonatan N Feb 1 '14 at 22:57

this sounds something like the "K shortest path routing problem"

  • $\begingroup$ @Juho it seems to me you can use $k$ shortest paths for not enumerating all paths via naive brute force. those that are too short are "thrown out" but at least the longer ones are not enumerated to find the solution. open to any better ideas, wink =) $\endgroup$ – vzn Feb 6 '14 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.