# DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk.

My question is that, say we have a DAG (directed acyclic graph), can DFS be a solution to the problem? I understand that native DFS would fail for the original problem as if there exists a cycle then we cannot traverse over the cycle to increase the path length from source to destination.

I've written the code tweaking DFS which I think solves the problem for a DAG.

I've used the inputs from a similar example, and have also compared the code both of which are based on the same algorithm.

//Pseudocode below:

public void printPossiblePaths(int u, int v, int k, int count, Queue queue) {
Mark u as visited;

foreach vertex w adjacent to u {
If w is not visited {
If count equals k before reaching 'v', ignore this vertex;

if (count==k) {
Print the path followed using the elements in the queue;
Remove last element from the queue;
return;
}
// Recur with the source as the new vertex and the updated queue
printPossiblePaths(w, v, k, count, queue);
}
}
Mark u as unvisited;
}


Gist of the algo:

1) Do a depth first search from the source vertex counting the edges as you go to.

2) Once you have traversed the k-edges, check if the node if we've arrived at the 'v'th node, otherwise come out of that path and check for other paths.

3) Similarly, if we do see the 'v'th node after 'k' edges, print the queue and check for for all other possible paths.

My question is : Is there a more efficient approach to achieve the same for a DAG or could we further tweak the code to handle cycles as well?

Consider an adjacency matrix A, where A[i][j] is 1 if there is an edge between i and j, and 0 otherwise.
Then, it can be proved that the number of paths of length k between i and j is just the [i][j] entry of A^k.
Thus the solution would be to build A and construct A^k using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.
The final complexity would simply be $O(V^3 logk)$