Print all paths from a given source to a destination in Python
In this article, we will learn how to print all the paths from a given source to a destination in Python.
We have given a graph, source vertex, and destination vertex.
This problem also commonly known as “Print all paths between two nodes”.
Depth First Search
- First, start with the source vertex ‘s’ and move to the next vertex.
- We observe the new problem is to find the route from the current vertex to the destination.
- We need to keep an eye on the visited nodes to avoid cycles.
- Add the current vertex to the result to keep track of the path from the source.
- Print the route when you reach the destination.
- Now go to the next node in the adjacent list in step 1 and repeat all the steps (loop)
For more understanding see the code below:
#Python program for Depth First Search from collections import defaultdict #This class shows a directed graph class Graph: def __init__(self,vertices): self.V= vertices self.graph = defaultdict(list) #this function adds an edge to the graph def addEdge(self,u,v): self.graph[u].append(v) def printAllPathsUtil(self, u, d, visited, path): # checking all the visited nodes visited[u]= True path.append(u) if u ==d: print path else: for i in self.graph[u]: if visited[i]==False: self.printAllPathsUtil(i, d, visited, path) path.pop() visited[u]= False # Printing all paths from sourse to destination def printAllPaths(self,s, d): #Marking all the vertices as not visited visited =[False]*(self.V) #Create an array to store paths path =  #Calling a recursive function for printing all paths self.printAllPathsUtil(s, d,visited, path) #Creating a graph as shown in the above figure g = Graph(4) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(0, 3) g.addEdge(2, 0) g.addEdge(2, 1) g.addEdge(1, 3) s = 2 ; d = 3 print (" These are the all unique paths from node %d to %d : " %(s, d)) g.printAllPaths(s, d)
These are the all unique paths from node 2 to 3 2 0 1 3 2 0 3 2 1 3