Do you think IIT Guwahati certified course can help you in your career?
Introduction
Here, we'll understand a problem: All possible walks from a source to a destination with exactly k edges. We will use both brute force and efficient approach which includes Dynamic Programming. We shall implement the program with different languages.
Starting with the adjacency matrix adjacent and raising it to a power of K delivers the value within the adjacency matrix as the path of length K is the fundamental concept in solving this problem.
First, we will understand the problem. All possible walks from a source to a destination with exactly k edges
Problem Statement
We need to determine the number of routes from source u to destination v that have precisely k edges given a directed graph.
Starting with the adjacency matrix adj and raising it to a power of K delivers the value within the adjacency matrix as the path of length K is the fundamental concept in solving this problem.
We utilize the adjacency matrix of the supplied graph, where the value of adj[i][j] indicates whether there is an edge in the graph connecting vertex I to vertex j. If the value is 1, then there is an edge in the graph from vertex I to vertex j; otherwise, if the value is 0, then there is no edge in the graph.
Explanation with Example
Let's use the example of a graph with 6 vertices (0, 1, 2, 3, 4, and 5) and edges to better grasp the issue. Find the total number of pathways that have two edges that connect vertex 0 and vertex 2. An illustration of the graph is shown below:
We may infer from the following graph that there are two pathways leading from vertex 0 to vertex 2, each with two edges: 0-->1-->2 and 0—>3—>2. By examining the graph's adjacency matrix, we may discover the same.
Brute Force
In brute force we have to create a recursive function that takes the value of vertex(current and destination) and the vertex count.
After that we call the recursion function where we make the value of k as k-1 for all adjacent vertices of a current vertex.
Check the current vertex is the destination or not when the value is 0. If it is destination output = 1.
Implementation in Java
// Java program to count walks from a to b with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class RanPaths {
static final int V = 4; // Number of vertices
// A recursive function to count walks from a
// to b with k edges
int count_walks(int graph[][], int a, int b, int k){
// Base cases
if (k == 0 && a == b)
return 1;
if (k == 1 && graph[a][b] == 1)
return 1;
if (k <= 0)
return 0;
// Initialize result
int count = 0;
for (int i = 0; i < V; i++)
if (graph[a][i] == 1) // Check if is adjacent of a
count += count_walks(graph, i, b, k - 1);
return count;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception
{
int graph[][] = new int[][] { { 0, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 0, 1, 0, 1 },
{ 1, 0, 0, 0 } };
int a = 0, b = 3, k = 2;
RanPaths k = new RanPaths();
System.out.println(k.count_walks(graph, a, b, k));
}
}
You can also try this code with Online Java Compiler
The above program has an O(V^k) worst-case time complexity, where V is the number of vertices in the provided graph. By creating a recursion tree, we can quickly assess the time complexity. The worst case scenario is for an entire graph. In the worst situation, the recursion tree's inner nodes would all have exactly n children.
Space Complexity
O(V) space is required to store the stack space and the visited array.
Using Dynamic Programming Approach
In the dynamic programming technique, the number of pathways is stored in a 3D matrix table called dp[i][j][e], which holds the number of paths from I to j with precisely e edges.
Starting with e=0 and filling the table up to e=k, we fill the table from the bottom up. Then, our solution is kept in dp[u][v][k], where u denotes the source, the number of edges connecting the source and destination, k, and the destination, v, are also given.
Implementation in Python
# may count the number of pathways from source to
# destination that have k edges.*/
def all_possible_walks(graph, u, v, edge):
if(edge == 0 and u == v): return 1
if(edge == 1 and graph[u][v]): return 1
if(edge <= 0): return 0
count = 0
# Loop for edges with number from 0 to k
for i in range(0, 5):
if(graph[u][i]):
count += all_possible_walks(graph, i, v, edge-1)
return count
# Let's construct the graph
graph = [[0, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[0, 1, 0, 0, 0]]
edge = 4
u = 0
v = 2
print(all_possible_walks(graph, u, v, edge))
edge = 3
u = 2
v = 2
if(u == v):
edge += 1
print(all_possible_walks(graph, u, v, edge))
You can also try this code with Online Python Compiler
O(V^3 k), where V is the number of graph vertices, and K denotes the number of edges.
Explanation:
We started with e=0, up to e=k. Then, our solution is kept in dp[u][v][k], where u denotes the source, v is the destination, and k is the number of edges that connect the source and destination.
Auxiliary Space
O(V^2 k), where V is the number of graph vertices, and K denotes the number of edges.
Explanation: We keep track of the number of pathways using a 3D matrix table, dp[i][j]. The number of pathways from I to j that have precisely e edges is stored in [e]. kept in dp [u] [v] [k] So space complexity is O(V^2 k).
Implementation in Java
// A Java application that Total_counts walks with precisely k edges from u to v
import java.util.*;
import java.lang.*;
import java.io.*;
class All_KPaths {
static final int Vertices = 4;
/*A simple recursive method to Total_count walks with k edges from u to v*/
int Total_Total_count_walks(int arr_graph[][], int u, int v, int k) {
if (k == 0 && u == v)
return 1;
if (k == 1 && arr_graph[u][v] == 1)
return 1;
if (k <= 0)
return 0;
// Initialize result
int Total_count = 0;
// Visit all of u's neighbours and repeat
for (int i = 0; i < Vertices; i++)
if (arr_graph[u][i] == 1)
Total_count += Total_Total_count_walks(arr_graph, i, v, k - 1);
return Total_count;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception {
/* Let's construct the array of graph seen in the diagram above.*/
int arr_graph[][] = new int[][] {
{
0,
1,
1,
1
},
{
0,
0,
0,
1
},
{
0,
0,
0,
1
},
{
0,
0,
0,
0
}
};
int u = 0, v = 3, k = 2;
All_KPaths p = new All_KPaths();
System.out.println(p.Total_Total_count_walks(arr_graph, u, v, k));
}
}
You can also try this code with Online Java Compiler
O(V^k), where V is the number of graph vertices, and K denotes the number of edges.
Explanation:
The above function has an O(V^k) worst-case time complexity, where V is the number of vertices in the provided graph. By creating a recursion tree, we can quickly assess the temporal complexity. The worst-case scenario is for a whole graph. In the worst situation, the recursion tree's interior nodes would all have precisely n children.
Auxiliary Space
O(V), where V is the number of graph vertices, and K denotes the number of edges.
Explanation: O(V) space is required to hold the stack space and the visited array.
Frequently Asked Questions
How do I extract every route from a DAG?
Using exponential, find every potential path across any graph. Backtracking can be used to fix the problem. We may use Depth First Search for DAGs (DFS). Start from any node in the DFS code, travel to the furthest dead end, and use an array or list to record all the nodes you visited along the way.
How does graph theory determine the path?
Finding a path between two vertices may be done using either a depth-first search (DFS) or a breadth-first search (BFS). In BFS (or DFS), use the first vertex as a source and proceed as normal (or DFS). Return true if our traverse finds the second vertex; otherwise, return false.
How do you tell if a graph component is tightly connected?
A directed graph is said to be highly linked if there is a path connecting each pair of the graph's vertices in each direction. The first vertex in the pair has a path leading to the second, and the second vertex has a path leading to the first.
How does walk graph theory work?
A walk is a collection of vertices and edges in a graph. A traversal of a graph is referred to as a "walk" after it is completed. There may be repeated vertices and edges in a walk. The length of a stroll is determined by how many edges are covered in it.
How do you determine whether a graph has strong connections?
Conducting a Depth-first search (DFS) or a Breadth-first search (BFS) beginning at each graph vertex is a straightforward solution. The graph is tightly linked if each DFS/BFS call reaches every other vertex in the graph.
Conclusion
We understood a problem. All possible walks from a source to a destination with exactly k edges. We implemented the programme in different languages.
Check out these questions. It will help you in exploring path-finding algorithms similar to Tarjan’s Algorithm.
518+ registered 
