Check if there is a path of more than k length from a source

Example

Input

source vertex = 0, k = 15
source vertex = 0, k = 31

Output

Yes
No

Explanation

In the given input graph, all the possible paths will be:

1. 0 -> 1 -> 3 -> 4 -> 2 => 23
2. 0 -> 1 -> 4 -> 2 => 17
3. 0 -> 1 -> 4 -> 3 => 24
4. 0 -> 2 -> 4 -> 3 => 19
5. 0 -> 2 -> 4 -> 1 -> 3 => 29
6. 0 -> 4 -> 1 -> 3 => 26
7. 0 -> 4 -> 2 => 9
8. 0 -> 4 -> 3 -> 1 => 24
    

The longest path as compared to distance will be 0 -> 2 -> 4 -> 1 -> 3. The distance, when you calculate, will come out to be 29. So, the output should be false for any value greater than 29.

Algorithm

With the help of backtracking, we solve this problem. We start from the source mentioned in the problem and explore all paths from that source or the current vertex. We keep a variable to track the distance covered from the source. If the distance becomes more than k, we return yes, or if no such path exists, we backtrack.

Let's start with the implementation of the code.

C++ Code

/* C++ Program: Check if there is a path of more than k length from a source */
#include<bits/stdc++.h>

using namespace std;

int vertices = 5;
typedef pair<int, int> iPair;
list<pair<int, int>> *adjacent = new list<iPair> [vertices];;

/* used to create an input graph */
void addEdge(int source, int destination, int distance) {
    adjacent[source].push_back(make_pair(destination, distance));
	adjacent[destination].push_back(make_pair(source, distance));
}

bool func(int sourceVertex, int k, vector<bool> &pathArray) {
    
    list<iPair>::iterator i;
	for (i=adjacent[sourceVertex].begin(); i!=adjacent[sourceVertex].end(); ++i) {
    	
		/* Getting adjacent vertex */
		int adjacentVertex = (*i).first;

		/* Getting corresponding distance */
		int distance = (*i).second;

		if (pathArray[adjacentVertex] == true)
			continue;

		if (distance >= k)
			return true;

		pathArray[adjacentVertex] = true;

		if (func(adjacentVertex, k-distance, pathArray))
			return true;

		pathArray[adjacentVertex] = false;
	}

	return false;
}

 
/* the main function returns true if such a path is possible */
bool checkPathWithLengthKOrMore(int sourceVertex, int k) {
    if (k <= 0) {
        return true;
    }
    
    vector<bool> pathArray(vertices, false);
    
	/* Adding source vertex to path */
	pathArray[sourceVertex] = 1;

	return func(sourceVertex, k, pathArray);
}

/* Main program */
int main() {
    
	/* creating the graph as shown in the input figure */
	addEdge(0, 1, 4);
	addEdge(0, 2, 8);
	addEdge(0, 4, 7);
	addEdge(1, 3, 8);
	addEdge(1, 4, 11);
	addEdge(2, 4, 2);
	addEdge(3, 4, 9);

	if (checkPathWithLengthKOrMore(0, 15)) {
    	cout << "Yes\n";
	}
	else {
    	cout << "No\n";
	}

	if (checkPathWithLengthKOrMore(0, 31)) {
    	cout << "Yes\n";
	}
	else {
    	cout << "No\n";
	}

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python Code

# Python Program: Check if there is a path of more than k length from a source

vertices = 15
adjacent = [[] for i in range(vertices)]

# used to create an input graph
def addEdge(source, destination, distance):
	adjacent[source].append([destination, distance])
	adjacent[destination].append([source, distance])

# the main function returns true if such a path is possible
def checkPathWithLengthKOrMore(sourceVertex, k):
    if (k <= 0):
        return True;
    pathArray = [False]*vertices
    
    # Adding source vertex to path
    pathArray[sourceVertex] = 1
    
    return func(sourceVertex, k, pathArray)
    
def func(sourceVertex, k, pathArray):
    i=0;
    while i != len(adjacent[sourceVertex]):
        
        # Getting adjacent vertex
        adjacentVertex = adjacent[sourceVertex][i][0]
        
        # Getting corresponding distance
        distance = adjacent[sourceVertex][i][1]
        i += 1
        
        if (pathArray[adjacentVertex] == True):
            continue
        
        if (distance >= k):
            return True
            
        pathArray[adjacentVertex] = True
        
        if (func(adjacentVertex, k-distance, pathArray)):
            return True
            
        pathArray[adjacentVertex] = False
        
    return False;

 
# Main program
if __name__ == '__main__':

	# creating the graph as shown in the input figure
	addEdge(0, 1, 4)
	addEdge(0, 2, 8)
	addEdge(0, 4, 7)
	addEdge(1, 3, 8)
	addEdge(1, 4, 11)
	addEdge(2, 4, 2)
	addEdge(3, 4, 9)

    # printing the desired output
	if checkPathWithLengthKOrMore(0, 15):
		print("Yes")
	else:
		print("No")

	if checkPathWithLengthKOrMore(0, 31):
		print("Yes")
	else:
		print("No")

You can also try this code with Online Python Compiler

Run Code

Input

source vertex = 0, k = 15
source vertex = 0, k = 31

Output

Yes
No

Complexities

Time complexity

O(N!), where N means the number of the vertex in the graph.

Reason: In the worst case, we must traverse every possible path. This occurs when each node is interconnected with the other. Let’s start from the source node we have n-1 adjacent nodes for the worst-case scenario. The time required for a path to connect will be 2. After selecting a node out of n-1 adjacent nodes, we are left with n-2 adjacent nodes and so on at every step of selecting a node, our selection reduces by 1 node. So, the time complexity of this algorithm is 2(n-1)*(n-1)!, which can be written as O(n!).

Space complexity

O(N), where N means the number of the vertex in the graph.

Reason: We need an array of size N to save pathArray and adjacent vertex count to keep track of the movement of the graph.

Check out this problem - 8 Queens Problem

Frequently Asked Questions

Why do we need backtracking?

Crosswords, verbal arithmetic, Sudoku, and many other puzzles that need constraint fulfillment can all be solved using backtracking. It is frequently the most practical technique for parsing the knapsack problem and other combinatorial optimization issues.

What are the limitations of backtracking?

Backtracking has the disadvantage of requiring extra work. Even if conflicting values for variables are found during intelligent backtracking, they are not stored for quick detection of the same conflict in a subsequent calculation.

What are the advantages of using backtracking?

Due to its brute-force approach, backtracking can almost fix all possible problems. This can be used to find all the possible solutions which exist.

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

Is backtracking recursive?

Backtracking can also be referred to as a type of recursion. This is because until we either find the solution or reach the final state, the process of selecting the best possible outcome from the available outcome is repeated.

Conclusion

In the article, we have to check if there is a path of more than k length from a source. We hope this article will help you understand the concept of Backtracking. Check out our other blogs on this topic:

• Backtracking
• Backtracking and Recursion
• Backtracking: The Knight’s Tour Problem
• Min-Max Algorithm
• N-Queen
• Generate Parentheses
• Sudoku Solver
• 8 Queens Problem Using Backtracking
   

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!