Given a directed graph represented as an adjacency matrix and an integer ‘k’, the task is to find all the vertex pairs that are connected with exactly ‘k’ edges.
Also, find the number of ways in which the two vertices can be linked in exactly k edges.
Examples :
Input : k = 3 and graph : 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 Output : 1 -> 4 in 1 way(s) 1 -> 5 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 3 -> 2 in 1 way(s) 3 -> 4 in 1 way(s) 3 -> 5 in 1 way(s) 4 -> 3 in 1 way(s) 5 -> 1 in 1 way(s) 5 -> 3 in 1 way(s) Input : k = 2 and graph : 0 0 0 1 0 1 0 1 0 Output : 2 -> 2 in 1 way(s) 3 -> 1 in 1 way(s) 3 -> 3 in 1 way(s)
Approach :
- We will multiply the adjacency matrix with itself ‘k’ number of times.
- In the resultant matrix, res[i][j] will be the number of ways in which vertex ‘j’ can be reached from vertex ‘i’ covering exactly ‘k’ edges.
Below is the implementation of the above approach :
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to multiply two square matricesvector<vector<int>> multiplyMatrices( vector<vector<int>> arr1, vector<vector<int>> arr2) { int order = arr1.size(); vector<vector<int>> ans(order, vector<int>(order)); for(int i = 0; i < order; i++) { for(int j = 0; j < order; j++) { for(int k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans;}// Function to find all the pairs that// can be connected with exactly 'k' edgesvoid solve(vector<vector<int>> arr, int k) { vector<vector<int>> res( arr.size(), vector<int>(arr[0].size())); // Copying arr to res, // which is the result for k=1 for(int i = 0; i < res.size(); i++) for(int j = 0; j < res.size(); j++) res[i][j] = arr[i][j]; // Multiplying arr with itself // the required number of times for(int i = 2; i <= k; i++) res = multiplyMatrices(res, arr); for(int i = 0; i < res.size(); i++) for(int j = 0; j < res.size(); j++) // If there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i][j] > 0) { cout << i << " -> " << j << " in " << res[i][j] << " way(s)" << endl; }}// Driver codeint main(int argc, char const *argv[]){ vector<vector<int>> arr(5, vector<int>(5)); arr[0][1] = 1; arr[1][2] = 1; arr[2][3] = 1; arr[2][4] = 1; arr[3][0] = 1; arr[4][2] = 1; int k = 3; solve(arr, k);}// This code is contributed by sanjeev2552 |
Java
// Java implementation of the approachpublic class KPaths { // Function to multiply two square matrices static int[][] multiplyMatrices(int[][] arr1, int[][] arr2) { int order = arr1.length; int[][] ans = new int[order][order]; for (int i = 0; i < order; i++) { for (int j = 0; j < order; j++) { for (int k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans; } // Function to find all the pairs that // can be connected with exactly 'k' edges static void solve(int[][] arr, int k) { int[][] res = new int[arr.length][arr[0].length]; // copying arr to res, // which is the result for k=1 for (int i = 0; i < res.length; i++) for (int j = 0; j < res.length; j++) res[i][j] = arr[i][j]; // multiplying arr with itself // the required number of times for (int i = 2; i <= k; i++) res = multiplyMatrices(res, arr); for (int i = 0; i < res.length; i++) for (int j = 0; j < res.length; j++) // if there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i][j] > 0) System.out.println(i + " -> " + j + " in " + res[i][j] + " way(s)"); } // Driver code public static void main(String[] args) { int[][] arr = new int[5][5]; arr[0][1] = 1; arr[1][2] = 1; arr[2][3] = 1; arr[2][4] = 1; arr[3][0] = 1; arr[4][2] = 1; int k = 3; solve(arr, k); }} |
Python3
# Python3 implementation of the approach# Function to multiply two square matricesdef multiplyMatrices(arr1, arr2): order = len(arr1) ans = [[0 for i in range(order)] for j in range(order)] for i in range(order): for j in range(order): for k in range(order): ans[i][j] += arr1[i][k] * arr2[k][j] return ans# Function to find all the pairs that# can be connected with exactly 'k' edgesdef solve(arr, k): res = [[0 for i in range(len(arr))] for j in range(len(arr))] # Copying arr to res, # which is the result for k=1 for i in range(len(arr)): for j in range(len(arr)): res[i][j] = arr[i][j] # Multiplying arr with itself # the required number of times for i in range(2, k+1): res = multiplyMatrices(res, arr) for i in range(len(arr)): for j in range(len(arr)): # If there is a path between 'i' # and 'j' in exactly 'k' edges if (res[i][j] > 0): print(i, "->", j, "in", res[i][j], "way(s)")# Driver Codeif __name__ == "__main__": arr = [1, 2, 3, 4] arr = [[0 for i in range(5)] for j in range(5)] arr[0][1] = 1 arr[1][2] = 1 arr[2][3] = 1 arr[2][4] = 1 arr[3][0] = 1 arr[4][2] = 1 k = 3 solve(arr, k) # This code is contributed by kirtishsurangalikar |
C#
// C# implementation of the approachusing System;class KPaths{ // Function to multiply two square matrices static int[,] multiplyMatrices(int[,] arr1, int[,] arr2) { int order = arr1.GetLength(0); int[,] ans = new int[order, order]; for (int i = 0; i < order; i++) { for (int j = 0; j < order; j++) { for (int k = 0; k < order; k++) { ans[i, j] += arr1[i, k] * arr2[k, j]; } } } return ans; } // Function to find all the pairs that // can be connected with exactly 'k' edges static void solve(int[,] arr, int k) { int[,] res = new int[arr.GetLength(0), arr.GetLength(1)]; // copying arr to res, // which is the result for k = 1 for (int i = 0; i < res.GetLength(0); i++) for (int j = 0; j < res.GetLength(1); j++) res[i, j] = arr[i, j]; // multiplying arr with itself // the required number of times for (int i = 2; i <= k; i++) res = multiplyMatrices(res, arr); for (int i = 0; i < res.GetLength(0); i++) for (int j = 0; j < res.GetLength(1); j++) // if there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i,j] > 0) Console.WriteLine(i + " -> " + j + " in " + res[i, j] + " way(s)"); } // Driver code public static void Main(String[] args) { int[,] arr = new int[5, 5]; arr[0, 1] = 1; arr[1, 2] = 1; arr[2, 3] = 1; arr[2, 4] = 1; arr[3, 0] = 1; arr[4, 2] = 1; int k = 3; solve(arr, k); } } // This code is contributed by Rajput-Ji |
Javascript
<script>// javascript implementation of the approach// Function to multiply two square matricesfunction multiplyMatrices(arr1, arr2){ var order = arr1.length; var ans = Array(order).fill(0).map(x => Array(order).fill(0)); for (var i = 0; i < order; i++) { for (var j = 0; j < order; j++) { for (var k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans;}// Function to find all the pairs that// can be connected with exactly 'k' edgesfunction solve(arr , k){ var res = Array(arr.length).fill(0).map(x => Array(arr[0].length).fill(0)); // copying arr to res, // which is the result for k=1 for (var i = 0; i < res.length; i++) for (var j = 0; j < res.length; j++) res[i][j] = arr[i][j]; // multiplying arr with itself // the required number of times for (var i = 2; i <= k; i++) res = multiplyMatrices(res, arr); for (var i = 0; i < res.length; i++) for (var j = 0; j < res.length; j++) // if there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i][j] > 0) document.write(i + " -> " + j + " in " + res[i][j] + " way(s)<br>");}// Driver codevar arr = Array(5).fill(0).map(x => Array(5).fill(0));arr[0][1] = 1;arr[1][2] = 1;arr[2][3] = 1;arr[2][4] = 1;arr[3][0] = 1;arr[4][2] = 1;var k = 3;solve(arr, k);// This code is contributed by shikhasingrajput</script> |
Output
0 -> 3 in 1 way(s) 0 -> 4 in 1 way(s) 1 -> 0 in 1 way(s) 1 -> 2 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 2 -> 4 in 1 way(s) 3 -> 2 in 1 way(s) 4 -> 0 in 1 way(s) 4 -> 2 in 1 way(s)
The time complexity of the above code can be reduced for large values of k by using matrix exponentiation. The complexity can be changed from O(n^3 * k) to O(n^3 * log k)
Implementation:
C++
#include <iostream>#include <vector>using namespace std;// Function to multiply two square matricesstatic vector<vector<int> >multiplyMatrices(vector<vector<int> > &arr1, vector<vector<int> > &arr2){ int order = arr1.size(); vector<vector<int> > ans(order, vector<int>(order)); for (int i = 0; i < order; i++) { for (int j = 0; j < order; j++) { for (int k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans;}vector<vector<int> > identity(int n){ vector<vector<int> > r(n, vector<int>(n)); for (int i = 0; i < n; i++) r[i][i] = 1; return r;}vector<vector<int> > power(vector<vector<int> >& x, int y, int n){ vector<vector<int> > res = identity(n); while (y > 0) { if ((y & 1) == 1) res = multiplyMatrices(res, x); // y must be even now // y = y / 2 y = y >> 1; x = multiplyMatrices(x, x); } return res;}// Function to find all the pairs that// can be connected with exactly 'k' edgesvoid solve(vector<vector<int> > &arr, int k){ vector<vector<int> > res(arr.size(), vector<int>(arr[0].size())); res = power(arr, k, arr[0].size()); for (int i = 0; i < res.size(); i++) { for (int j = 0; j < res.size(); j++) { // if there is a path between 'i' and 'j' in // exactly 'k' edges if (res[i][j] > 0) { cout << i << " -> " << j << " in " << res[i][j] << " way(s)" << endl; } } }}int main(){ vector<vector<int> > arr(5, vector<int>(5)); arr[0][1] = 1; arr[1][2] = 1; arr[2][3] = 1; arr[2][4] = 1; arr[3][0] = 1; arr[4][2] = 1; int k = 3; solve(arr, k); return 0;}// This code is contributed by Tapesh (tapeshdua420) |
Java
class KPaths { // Function to multiply two square matrices static int[][] multiplyMatrices(int[][] arr1, int[][] arr2) { int order = arr1.length; int[][] ans = new int[order][order]; for (int i = 0; i < order; i++) { for (int j = 0; j < order; j++) { for (int k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans; } // Function to find all the pairs that // can be connected with exactly 'k' edges static void solve(int[][] arr, int k) { int[][] res = new int[arr.length][arr[0].length]; res = power(arr, k, arr[0].length); for (int i = 0; i < res.length; i++) for (int j = 0; j < res.length; j++) // if there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i][j] > 0) System.out.println(i + " -> " + j + " in " + res[i][j] + " way(s)"); } static int[][] power(int x[][], int y, int n) { // MATRIX EXPONENTIATION // Initialize result int res[][] = identity(n); while (y > 0) { if ((y & 1) == 1) res = multiplyMatrices(res, x); // y must be even now // y = y / 2 y = y >> 1; x = multiplyMatrices(x, x); } return res; } static int[][] identity(int n) { // returns identity matrix of order n int r[][] = new int[n][n]; for (int i = 0; i < n; i++) r[i][i] = 1; return r; } // Driver code public static void main(String[] args) { int[][] arr = new int[5][5]; arr[0][1] = 1; arr[1][2] = 1; arr[2][3] = 1; arr[2][4] = 1; arr[3][0] = 1; arr[4][2] = 1; int k = 3; solve(arr, k); }} |
Python3
# Function to multiply two square matricesdef multiplyMatrices(arr1, arr2): order = len(arr1) ans = [[0 for i in range(order)] for j in range(order)] for i in range(order): for j in range(order): for k in range(order): ans[i][j] += arr1[i][k] * arr2[k][j] return ansdef identity(n): r = [[0 for i in range(n)] for j in range(n)] for i in range(n): r[i][i] = 1 return rdef power(x, y, n): res = identity(n) while y > 0: if ((y & 1) == 1): res = multiplyMatrices(res, x) # y must be even now y = y >> 1 x = multiplyMatrices(x, x) return res# Function to find all the pairs that# can be connected with exactly 'k' edgesdef solve(arr, k): res = [[0 for i in range(len(arr))] for j in range(len(arr))] res = power(arr, k, len(arr[0])) for i in range(len(res)): for j in range(len(res)): # if there is a path between 'i' and 'j' in # exactly 'k' edges if res[i][j] > 0: print("{} -> {} in {} way(s)".format(i, j, res[i][j]))if __name__ == "__main__": arr = [[0 for i in range(5)] for j in range(5)] arr[0][1] = 1 arr[1][2] = 1 arr[2][3] = 1 arr[2][4] = 1 arr[3][0] = 1 arr[4][2] = 1 k = 3 solve(arr, k) # This code is contributed by Tapesh (tapeshdua420) |
C#
// C# implementation of the above approach: using System;class KPaths { // Function to multiply two square matrices static int[,] multiplyMatrices(int[,] arr1, int[,] arr2) { int order = arr1.GetLength(0); int[,] ans = new int[order,order]; for (int i = 0; i < order; i++) { for (int j = 0; j < order; j++) { for (int k = 0; k < order; k++) { ans[i, j] += arr1[i, k] * arr2[k, j]; } } } return ans; } // Function to find all the pairs that // can be connected with exactly 'k' edges static void solve(int[,] arr, int k) { int[,] res = new int[arr.GetLength(0), arr.GetLength(1)]; res = power(arr, k, arr.GetLength(0)); for (int i = 0; i < res.GetLength(0); i++) for (int j = 0; j < res.GetLength(1); j++) // if there is a path between 'i' // and 'j' in exactly 'k' edges if (res[i, j] > 0) Console.WriteLine(i + " -> " + j + " in " + res[i, j] + " way(s)"); } static int[,] power(int [,]x, int y, int n) { // MATRIX EXPONENTIATION // Initialize result int [,]res = identity(n); while (y > 0) { if ((y & 1) == 1) res = multiplyMatrices(res, x); // y must be even now // y = y / 2 y = y >> 1; x = multiplyMatrices(x, x); } return res; } static int[,] identity(int n) { // returns identity matrix of order n int [,]r = new int[n, n]; for (int i = 0; i < n; i++) r[i, i] = 1; return r; } // Driver code public static void Main(String[] args) { int[,] arr = new int[5, 5]; arr[0, 1] = 1; arr[1, 2] = 1; arr[2, 3] = 1; arr[2, 4] = 1; arr[3, 0] = 1; arr[4, 2] = 1; int k = 3; solve(arr, k); }}// This code is contributed by PrinciRaj1992 |
Javascript
//JS code for the above approach// Function to multiply two square matricesfunction multiplyMatrices(arr1, arr2) { // MATRIX EXPONENTIATION // Initialize result let order = arr1.length; let ans = []; for (let i = 0; i < order; i++) { ans[i] = []; for (let j = 0; j < order; j++) { ans[i][j] = 0; } } for (let i = 0; i < order; i++) { for (let j = 0; j < order; j++) { for (let k = 0; k < order; k++) { ans[i][j] += arr1[i][k] * arr2[k][j]; } } } return ans;}function identity(n) { let r = []; for (let i = 0; i < n; i++) { r[i] = []; for (let j = 0; j < n; j++) { r[i][j] = 0; } } for (let i = 0; i < n; i++) { r[i][i] = 1; } return r;}function power(x, y, n) { let res = identity(n); while (y > 0) { if ((y & 1) === 1) { res = multiplyMatrices(res, x); } y = y >> 1; x = multiplyMatrices(x, x); } return res;} // Function to find all the pairs that // can be connected with exactly 'k' edgesfunction solve(arr, k) { let res = []; for (let i = 0; i < arr.length; i++) { res[i] = []; for (let j = 0; j < arr[0].length; j++) { res[i][j] = 0; } } res = power(arr, k, arr[0].length); for (let i = 0; i < res.length; i++) { for (let j = 0; j < res.length; j++) { if (res[i][j] > 0) { console.log(`${i} -> ${j} in ${res[i][j]} way(s)`); } } }}let arr = [];for (let i = 0; i < 5; i++) { arr[i] = []; for (let j = 0; j < 5; j++) { arr[i][j] = 0; }}arr[0][1] = 1;arr[1][2] = 1;arr[2][3] = 1;arr[2][4] = 1;arr[3][0] = 1;arr[4][2] = 1;let k = 3;solve(arr, k); |
Output
0 -> 3 in 1 way(s) 0 -> 4 in 1 way(s) 1 -> 0 in 1 way(s) 1 -> 2 in 1 way(s) 2 -> 1 in 1 way(s) 2 -> 3 in 1 way(s) 2 -> 4 in 1 way(s) 3 -> 2 in 1 way(s) 4 -> 0 in 1 way(s) 4 -> 2 in 1 way(s)
Complexity Analysis:
- Time Complexity: O(n3 * logk)
- Space Complexity: O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
