# Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) from a node i to a node j of length p. For instance, i->j is of length 2 if the edge i->j exists, i->k->j is of length 3, etc...). The graph is either given as an adjacency matrix or adjacency lists. In my very special case, I'm searching for cycles 0->...->0 of given length, but I'm pretty sure I'm gonna need the more general case i->...->j.

Right now, I'm dynamically storing paths from k to j of length q in a matrix Z[k][q], and since I need Z[i][p], I first compute all the Z[j][p-1] for i->j, then append i to them.

The problem is that this approach uses an awful lot of memory and doesn't scale very nicely for large graphs. Any advice on this ?

• Note that the length of a path is usually defined to be the number of edges in the path, not the number of vertices. Thus, if there is an edge from $i$ to $j$, then those vertices are normally said to be at distance 1, not 2. – David Richerby May 25 '15 at 8:04
• What do you mean by "efficiently enumerating"? There can be exponentially many paths of a given length in a graph (consider the complete graph) so any algorithm must take at least exponential time in total, in the worst case. For enumeration algorithms, we normally talk about working with polynomial delay, i.e., the algorithm does at most a polynomial amount of work between each output in the enumeration. – David Richerby May 25 '15 at 8:05
• Thanks for the remark. That's of course what I meant and I was wondering how to implement an algorithm that wouldn't consume as much memory as mine while being as efficient (since I do not seem to be doing any unnecessary computations). – Mrktn May 25 '15 at 10:21
• The "Related" column to the right contains several closely related questions. – Raphael May 25 '15 at 10:35

Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using pointers, so that you only use $O(1)$ storage per path, letting paths share their common suffixes (if you do not do this already).
• @Mrktn What I am hinting at is that instead of storing each path explicitly as a list of vertices (requiring $O(n)$ space) you store just a single vertex with a pointer to the next, like in a linked list. Since in the DP you obtain each path as the extension of another path, you can let all paths that are obtained by extending a given path share the same tail section. – Tom van der Zanden May 25 '15 at 11:18