# Number of paths with k edges using Dynamic programming and Divide and Conquer

Reading time: 40 minutes

Given a directed graph, we need to find the number of paths with exactly **k** edges from source **u** to the destination **v**.

We use `adjacency matrix`

of the given graph in which value of `adj[i][j]`

represents if there is an edge from vertex `i`

to vertex `j`

in the graph. If the value is `1`

then there is an edge from vertex `i`

to vertex `j`

else, if value is `0`

then there is no edges from vertex `i`

to vertex `j`

in the graph.

To understand the problem let's take an example of a graph with 6 vertices {0, 1, 2, 3, 4, 5} and edges. Now let's find number of paths from vertex `0`

to vertex `2`

with 2 edges. Below a diagram of the graph is given:

From the above graph we can conclude that there are 2 paths from vertex `0`

to vertex `2`

with 2 edges, one is `0-->1-->2`

and the other is `0-->3-->2`

. The same we can find by the analysis of adjacency matrix of the graph.

To solve this problem, we will see three approaches.

- First one is naive or brute force approach which takes O(V
^{k}) time - second one is Dynamic programming approach which takes O(V
^{3}k) time - the last is Divide and Conquer approach which takes O(V
^{3}log k) time.

# Naive approach (Brute Force)

This is the simple way to start from the source, go to all the adjacent vertices and recur for adjacent vertices for k as k-1, source as adjacent vertices. When k becomes 0 and we reach to the destination, then we count it as one of the solution.

```
int numberOfPathsNaive(std::vector< std::vector<int> > adj, int u, int v, int k)
{
int __v = adj.size();
if(k == 0 && u == v)
return 1;
if(k == 1 && adj[u][v])
return 1;
if(k <= 0)
return 0;
int res = 0;
for(int i = 0; i < __v; ++ i)
{
if(adj[u][i])
{
res += numberOfPathsNaive(adj, i, v, k - 1);
}
}
return res;
}
```

The naive approach takes O(V^{k}) time as in the adjacency matrix we check each and every vertices for a path this takes O(V) time each, and we do the this k times. The worst occurs for a complete graph when for each vertex there are V edges going out from them.

# Dynamic Programming approach

In dynamic programing approach we use a 3D matrix table to store the number of paths, **dp[i][j][e]** stores the number of paths from `i`

to `j`

with exactly `e`

edges.

We fill the table in bottom up manner, we start from `e=0`

and fill the table till `e=k`

. Then we have our answer stored in `dp[u][v][k]`

where `u`

is source, `v`

is destination and `k`

is number edges between path from source to destination.

Here we use the recurrence as:

```
if(e>1)
for(int b = 0; b < __v ; ++b)
if(adj[i][b])
dp[i][j][e] += dp[b][j][e - 1];
```

The time complexity of DP approach is O(V^{3}k).

# Implementation

**Code in C++11**

```
// C++ Program to find the number of paths
// with k edges from source to dest with DP appraoch.
#include<iostream>
#include<vector>
int numberOfPathsdp(std::vector<std::vector<int>> adj, int u, int v, int k)
{
int __v = adj.size();
int dp[__v][__v][k + 1];
for(int e = 0;e <= k; ++ e)
{
for(int i = 0;i < __v; ++ i)
{
for(int j = 0;j < __v; ++ j)
{
// initialize
dp[i][j][e] = 0;
// base cases
if(e == 0 && i == j)
dp[i][j][e] = 1;
if(e == 1 && adj[i][j])
dp[i][j][e] = 1;
// go to adjacent edges only when number of edges is more than 1
if(e>1)
{
for(int b = 0; b < __v ; ++ b)
{
if(adj[i][b])
{
dp[i][j][e] += dp[b][j][e - 1];
}
}
}
}
}
}
// number of paths from u to v with k edges
return dp[u][v][k];
}
int main()
{
int _v, e;
std::cin >> _v >> e;
std::vector< std::vector<int> > adj(_v, std::vector<int>(_v));
int u, v;
for(int i = 0;i < e; ++ i)
{
std::cin >> u >> v;
adj[u][v] = 1;
}
int k;
std::cin >> u >> v >> k;
int res = numberOfPathsdp(adj, u, v, k);
std::cout << res << "\n";
return 0;
}
```

# Divide and Conquer approach

We can use divide and conquer approach to solve this problem in O(V^{3}log_{2}k) time, to this we use the fact that the number of paths of length `k`

from `u`

to `v`

is the `[u][v]`

th entry in the matrix (adj[V][V])^{k}.

The `k`

th power of a graph G is a graph with the same set of vertices as G and an edge between two vertices iff there is a path of length at most k between them. Since a path of length two between vertices u and v exists for every vertex w such that {u,w} and {w,v} are edges in G, the square of the adjacency matrix of G counts the number of such paths. Similarly, the `[u][v]`

th element of the `k`

th power of the adjacency matrix of G gives the number of paths of length k between vertices u and v.

To find (adj[V][V])^{k} we use the divide and conquer approach of finding `power(x, y)`

in O(log_{2}y) time, i.e. this algorithm is an application of fast matrix exponentiation.

```
// Function to compute adj raise to power k.
int power(std::vector<std::vector<int>> adj, int u, int v, int k)
{
int __v = adj.size();
std::vector<std::vector<int>> res(__v, std::vector<int>(__v));
for(int i = 0; i < __v; ++i)
res[i][i] = 1;
while (k > 0)
{
if (k % 2 == 1)
res = multiply(res, adj);
adj = multiply(adj, adj);
k /= 2;
}
// number of paths from u to v with k edges
return res[u][v];
}
```

# Implementation

**Code in C++11**

```
// C++ Program to find the number of paths
// with k edges from source to dest with Divide and Conquer appraoch.
#include <iostream>
#include <vector>
// A utility function to multiply two matrices
// a[][] and b[][]. Multiplication result is
// stored back in a[][]
std::vector<std::vector<int>> multiply(std::vector<std::vector<int>> a,
std::vector<std::vector<int>> b)
{
// Creating an auxiliary matrix to store elements
// of the multiplication matrix
int __v = a.size();
std::vector<std::vector<int>> mul(__v, std::vector<int>(__v));
for (int i = 0; i < __v; ++i)
{
for (int j = 0; j < __v; ++j)
{
mul[i][j] = 0;
for (int l = 0; l < __v; ++l)
mul[i][j] += a[i][l] * b[l][j];
}
}
return mul;
}
// Function to compute adj raise to power k.
int power(std::vector<std::vector<int>> adj, int u, int v, int k)
{
int __v = adj.size();
std::vector<std::vector<int>> res(__v, std::vector<int>(__v));
for(int i = 0; i < __v; ++i)
res[i][i] = 1;
while (k > 0)
{
if (k % 2 == 1)
res = multiply(res, adj);
adj = multiply(adj, adj);
k /= 2;
}
// number of paths from u to v with k edges
return res[u][v];
}
// function to find total number of paths
// with k edges.
int numberOfPathsDivideConquer(std::vector<std::vector<int>> adj, int u, int v, int k)
{
return power(adj, u, v, k);
}
int main()
{
int _v, e;
std::cin >> _v >> e;
std::vector<std::vector<int>> adj(_v, std::vector<int>(_v));
int u, v;
for (int i = 0; i < e; ++i)
{
std::cin >> u >> v;
adj[u][v] = 1;
}
int k;
std::cin >> u >> v >> k;
int res = numberOfPathsDivideConquer(adj, u, v, k);
std::cout << res << "\n";
return 0;
}
```

# Complexity

**Time Complexity**

- Brute force approach takes O(V
^{k}) time. - DP approach takes O(V
^{3}k) time. - Divide and Conquer approach takes O(V
^{3}log_{2}k) time.

**Space Complexity**

- Brute force approach takes O(V
^{2}) auxiliary space and O(V^{k}) stack space. - DP approach takes O(V
^{2}k) auxiliary space. - Divide and conquer takes O(V
^{2}) auxiliary space.