# Number of Walks from source to destination

Given a graph and two vertices src and dest, count the total number of paths from src to dest where the length of the path is k (there should be exactly k edges between them). Note that the graph is represented as an adjacency matrix.

For example, consider the following graph:

The number of paths from vertex 0 to vertex 3 with length 2 is 2 ({0->1->3} and {0->2->3}).

We have already discussed a O(V^{3} K) approach in count all possible walks from a source to a destination with exactly k edges. In this post, a O(V^{3} Log K) approach is discussed.

**Approach:** The idea is to compute a resultant matrix where *result = (graph) ^{k}*. The total number of paths from source to the destination of length k will then be simply

*result[src][dest]*. We use this technique to compute the exponentiation of the adjacency matrix of the given graph.

The recursion tree of power function used here for exponent = 7 looks like below:

Below is the implementation of the above approach:

**Output:**

Total number of walks: 2

**Time Complexity:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.