Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Explanation with Example
4.
Brute Force
4.1.
Implementation in Java
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Using Dynamic Programming Approach
5.1.
Implementation in Python
5.1.1.
Output
6.
Complexity Analysis 
6.1.
Time Complexity:
6.2.
Auxiliary Space
6.3.
Implementation in Java
6.3.1.
Output
7.
Complexity Analysis 
7.1.
Time Complexity:
7.2.
Auxiliary Space
8.
Frequently Asked Questions
8.1.
How do I extract every route from a DAG?
8.2.
How does graph theory determine the path?
8.3.
How do you tell if a graph component is tightly connected?
8.4.
How does walk graph theory work?
8.5.
How do you determine whether a graph has strong connections?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

All Possible Walks from a Source to a Destination with exactly k Edges

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

All Possible Walks from a Source to a Destination with exactly k Edges

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.

Problem Statement


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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

Explanation with Example

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));
    }
}

Output

2

Time Complexity

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))

Output

3

2

Complexity Analysis 

Time Complexity:

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));
    }
}

Output

2

Complexity Analysis 

Time Complexity:

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.


Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Comment here with any questions or concerns you may have about the post.

Happy Learning Ninja! 🥷

Previous article
Optimal read list for given number of days
Next article
What is the Sieve Method?
Live masterclass