Program to find if there is a path of more than k length from a source in Python

In this tutorial, we will learn about graph traversal and how to find the path(without cycle) from a source vertex to another vertex. There is a given graph, a starting (source) vertex, and a number K. We have to find if there is a path (without cycle) from a source vertex to any other vertex. And check whether this path’s distance is more than K or not.
If we find a path and its distance is more than K so simply return True otherwise False.

How to check if the path is more than ‘k’ or not

There is going to use Backtracking. First, we have to start from the starting vertex (source: s) to explore all the paths from the source vertex. we keep track and check the current distance. If the distance is more than K then we simply return True otherwise, we backtrack. At last, we track every path and did not find more than K so return False.

We have to make sure the path is simple and do not contain any cycle. Keep track current path into an array. Whenever we add a new vertex to the path, we have to check if it already exists or not in the current path. If it exists, then we ignore the edge.

Implementation of the idea

class graph:
    def __init__(self,v):
        self.v = v
        self.adj = [[] for i in range(v)]  #adj=adjacency
        
    def pathmorethanK(self,src,k):  # to check path is grathe
        path = [False]*self.v
        path[s] = 1
        
        return self.pathbacktrack(s,k,path)
    
    def pathbacktrack(self,s,k,path):
        if(k<0):
            return True
        i=0
        while i != len(self.adj[s]):
            v = self.adj[s][i][0] 
            w = self.adj[s][i][1] 
            i += 1
            
            if (path[v] == True):  
                continue 
                
            if (w > k): 
                return True 
            path[v] = True
            
            if (self.pathbacktrack(v, k-w, path)):  
                return True 
        
            path[v] = False
            
        return False 
    
    def addEdge(self,u, v, w): 
        self.adj[u].append([v, w])  # edge[u, v] and wieght w
        self.adj[v].append([u, w])
        
V = 5  #No of vertex
g = graph(V)  
  
g.addEdge(0, 1, 10)  #edge[u, v, w]
g.addEdge(0, 2, 5)  
g.addEdge(0, 4, 40)  
g.addEdge(1, 2, 20)  
g.addEdge(2, 3, 30)  
g.addEdge(2, 4, 20)  
g.addEdge(3, 4, 10)  

s = 0   # source vertex
k = int(input('Value of K: '))  # input for K
if g.pathmorethanK(s, k): 
    print("result: Yes") 
else: 
    print(" result: No")

OUTPUT:

Value of K: 99
result: Yes

Value of K: 100
result: No

Thanks for visiting codespeedy. I hope it helps you.

Also read:

• Generate a graph using Dictionary in Python