How to find all simple paths of no more than k lengths starting at a vertex in a directed graph?

Question

I am trying to find all simple paths up to a given length, and working on using BFS to solve this problem. However, I am not sure about the specific algorithm to use. It seems that BFS cannot easily solve this problem. All problems I found were about finding paths between two given vertexes.

However, I wonder how to find all simple paths that have lengths up to a given k, starting at a given vertex in a directed graph. No cycles are allowed.

k lengths means k hops, not the weights of paths.

For example, we have k = 3, and given vertex 1, we want to find paths of length of k = 1, k = 2, k = 3.

when k = 1, we have paths 12 and 13; when k = 2, we have paths 132 and 134; when k = 3, we don't find appropriate paths.

What algorithm can I use to solve the problem?

Answer 1

You would use a depth-first traversal for this. A recursive function is the natural choice for that. It would recur up to depth k and then produce the path it had traversed. At each recursive call make sure you don't add a node to the path that is already on the path. And when you get out of a recursive call, reduce the path accordingly.

Here is an implementation in JavaScript, where the recursive function takes as argument an adjacency list (to represent the graph), the current node, the value of k and the path as a Set (an ordered Hash Set).

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    if (k == 0) return yield [...path, node]; // We have a result
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with k=1, k=2 and k=3:
for (let k = 1; k <= 3; k++) {
    console.log("results for k =", k);
    for (const path of genPaths(adj, "1", k)) {
        console.log("  ", ...path);
    }
}
console.log("done");

Extending it...

The above function returns paths of exactly k lengths, and the main code uses it to get paths for several different lengths. If you are always interested in all shorter paths as well, even including the one with size 0 (just the starting node) then you could extend the function to do that all with one top-level call:

function* genPaths(adj, node, k, path=new Set) {
    if (path.has(node)) return; // cycle detected!
    yield [...path, node]; // We have a result (0 <= path size <= k)
    if (k == 0) return;
    path.add(node);
    for (const neighbor of adj[node]) {
        yield* genPaths(adj, neighbor, k - 1, path);
    }
    path.delete(node); // backtrack
}

// Demo
const adj = {
    "1": ["2", "3"],
    "2": [],
    "3": ["2", "4"],
    "4": ["3"]
};

// Finding paths with size <= 3:
for (const path of genPaths(adj, "1", 3)) {
    console.log("  ", ...path);
}
console.log("done");

Note that the size of a path is expressed as the number of edges on it, so [1] is a path of length 0, [1, 3] is a path of length 1, ...etc.

If you want to exclude the path with length 0, then just add a condition to the yield statement:

    if (path.length > 0) yield [...path, node];